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.
Implement:
```python def find_circle_num(M): ... ```
M is an $n \times n$ symmetric 0/1 matrix. Return the total number of friend circles (connected components) as an integer.
Constraints: - $1 \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.
Example
find_circle_num([[1, 1, 0], [1, 1, 1], [0, 1, 1]]) -> 1
All three people are transitively connected through person 1, forming a single friend circle.
Hints
- Think about what "friend circle" means in graph terms -- what standard graph concept does it correspond to?
- For the DFS approach, consider using a visited array and starting a new traversal from each unvisited node. For Union-Find, think about merging sets whenever $M[i][j] = 1$.
- In Union-Find, use path compression and union by rank to keep operations nearly $O(1)$. Count the number of distinct roots at the end.
Worked Solution
How to Think About It: This is the classic "number of connected components" problem, dressed up with a social-network story. The adjacency matrix is a graph where each person is a node and each friendship is an undirected edge. Friend circles are exactly the connected components. Two standard ways to count them: (1) run DFS/BFS from each unvisited node, incrementing a counter each time; or (2) use a Union-Find (disjoint set) structure to merge connected nodes and count the remaining distinct roots.
Contract: The entry function is find_circle_num(M). It takes the $n \times n$ symmetric 0/1 matrix and must return the integer count of connected components. (Note: it must be named exactly find_circle_num -- a helper with a different name will not be called by the grader.)
Algorithm (Union-Find): Initialize each person as their own parent. For each pair $(i, j)$ with $i < j$ and $M[i][j] = 1$, union their sets. At the end, count the number of distinct roots.
Solution (Union-Find, the entry function):
```python def find_circle_num(M): # M is an n x n symmetric 0/1 adjacency matrix (M[i][i] == 1). # Return the number of connected components (friend circles). n = len(M) parent = list(range(n))
def find(x): while parent[x] != x: parent[x] = parent[parent[x]] x = parent[x] return x
def union(a, b): ra, rb = find(a), find(b) if ra != rb: parent[ra] = rb
for i in range(n): for j in range(i + 1, n): if M[i][j] == 1: union(i, j)
return len({find(i) for i in range(n)}) ```
Alternative (DFS):
```python def find_circle_num_dfs(M): n = len(M) visited = [False] * n count = 0
def dfs(i): visited[i] = True for j in range(n): if M[i][j] == 1 and not visited[j]: dfs(j)
for i in range(n): if not visited[i]: dfs(i) count += 1 return count ```
Complexity:
- DFS/BFS: Time $O(n^2)$ -- every matrix entry is examined once across all traversals. Space $O(n)$ for the visited array (plus $O(n)$ recursion stack in the worst case).
- Union-Find: Time $O(n^2 \cdot \alpha(n))$, effectively $O(n^2)$ since the inverse Ackermann $\alpha(n) \le 5$ for any practical $n$. Space $O(n)$ for the parent array.
Both are $O(n^2)$ overall, which is optimal since you must read the entire matrix. DFS is simpler; Union-Find shines when edges arrive incrementally.
Intuition
This problem is a thin wrapper around one of the most fundamental graph concepts: counting connected components. The friendship matrix is just an adjacency matrix, and a "friend circle" is a connected component. Recognizing this translation instantly is the key skill -- many interview problems disguise standard graph questions behind domain-specific language (social networks, network connectivity, equivalence classes). Once you see through the disguise, you reach for one of two standard tools: DFS/BFS traversal or Union-Find.
In practice, the choice between DFS and Union-Find depends on context. If you have the full adjacency matrix upfront, DFS is dead simple and hard to mess up. But if friendships arrive as a stream of edges ("person A just befriended person B -- how many circles now?"), Union-Find is far superior because you can process each new edge in nearly constant time without re-traversing the graph. This streaming scenario comes up constantly in real systems -- monitoring cluster connectivity, tracking regime changes in correlation networks, or maintaining equivalence classes as new data arrives.