Counting Friend Circles
You are given an $n \times n$ adjacency matrix $M$ where $M[i][j] = 1$ means person $i$ and person $j$ are friends. Friendship is symmetric ($M[i][j] = M[j][i]$) and reflexive ($M[i][i] = 1$). A "friend circle" is a group of people who are all connected directly or transitively -- if A is friends with B, and B is friends with C, then A, B, and C are all in the same circle even if A and C are not directly friends.
Return the total number of friend circles.
Provide two solutions:
1. A DFS or BFS approach
2. A Union-Find approach
Analyze the time and space complexity of each.
**Constraints:**
-
\le n \le 1000$
- $M[i][j] \in \{0, 1\}$
- $M[i][j] = M[j][i]$ for all $i, j$
- $M[i][i] = 1$ for all $i$
**Example 1:**
Input:
```
M = [[1, 1, 0],
[1, 1, 0],
[0, 0, 1]]
```
Output: `2`
Explanation: Persons 0 and 1 are friends (same circle). Person 2 is alone. Two circles total.
**Example 2:**
Input:
```
M = [[1, 1, 0],
[1, 1, 1],
[0, 1, 1]]
```
Output: `1`
Explanation: Person 0 is friends with 1, and 1 is friends with 2, so all three are transitively connected. One circle.
Open the full interactive solver, hints, and worked solution →