The problem
Given n nodes and a list of undirected edges, count the number of connected components (separate groups).
Input: n = 5, friendships 0-1, 1-2, 3-4 Output: 2
Picture it
Picture people and the friendships between them. Everyone starts in their own circle of friends. Each friendship merges two circles into one (if they weren’t already the same). Start with n circles; every successful merge reduces the count by 1.
How to recognise it
- An undirected graph given as n nodes and a list of edges, and the question is how many separate groups it has.
- Nodes are joined by connection only, with no direction and no distances.
- Edges can be processed in any order, which suits a structure that merges groups.
- With up to 2,000 nodes and 5,000 edges the numbers are small, but the technique matters for 10^5 or more.
Start with brute force
Give each node a group label. For each edge, if the two ends have different labels, relabel every node of one group with the other label. The answer is the number of distinct labels.
def count_components_brute(n, edges):
label = list(range(n))
for a, b in edges:
la, lb = label[a], label[b]
if la != lb:
label = [la if x == lb else x for x in label]
return len(set(label))
Every merge rewrites all n labels, and there can be n − 1 merges, so time is O(V·E) in the worst case: about 10^7 steps for 2,000 nodes and 5,000 edges, but 10^10 for 10^5 of each. Space is O(V).
From brute force to the idea
- Find the waste. Relabelling n nodes just to say "these two groups are now one" is far too much work.
- Point instead of relabel. Give each group a single representative. Each node holds a
parent; following parents leads to the representative, found byfind. - Merge with one assignment. To join two groups, make one root the parent of the other:
parent[rb] = ra. The other nodes are not touched. - Keep the count. Start with
groups = n. Each edge whose ends have different roots merges two groups, so subtract 1. Edges inside an existing group change nothing. - Keep chains short.
parent[x] = parent[parent[x]]halves the path while walking, so laterfindcalls are quick.
The key idea: components = n − (number of successful merges), and a merge costs almost nothing.
The key idea
Union-find: components = n − (number of successful unions).
Python solution
def count_components(n, edges):
parent = list(range(n))
def find(x):
while parent[x] != x:
parent[x] = parent[parent[x]]
x = parent[x]
return x
groups = n
for a, b in edges:
ra, rb = find(a), find(b)
if ra != rb:
parent[rb] = ra
groups -= 1
return groupsIn the interactive version each line lights up as the animation runs, and you can type your own input to see the algorithm handle it.
Complexity
| Approach | Time | Space |
|---|---|---|
| Brute force | O(V·E): each merge rewrites up to V labels | O(V): the label list |
| Union-find (shown code) | O(V + E log V) at worst, close to O(V + E) in practice, because path halving keeps chains short | O(V): the parent list |
Edge cases
- No edges (
n = 5,[]): returns 5, since every node is alone. - One node (
n = 1): returns 1. - No nodes (
n = 0): returns 0. - Duplicate edges and self-loops (
n = 3,[[0,1],[0,1],[2,2]]): return 2. A repeated edge and a self-loop find equal roots and change nothing. - A chain (
[[0,1],[1,2],[3,4]]with n = 5): returns 2. - Isolated nodes count as groups, so n must be given and cannot be inferred from the edges.
Common mistakes
- Counting groups by looking only at nodes that appear in an edge, which forgets isolated nodes.
- Setting
parent[b] = ainstead ofparent[rb] = ra, which overwrites an earlier link and loses a merge. - Decrementing
groupsfor every edge, including ones inside a group. - Forgetting that
groupsstarts at n, not 0 or 1. - Doing a fresh DFS from every node without a visited set.
Edges arrive one by one. Return a list with the number of groups after each edge is added. For n = 4 and edges [[0,1],[1,0],[2,3],[1,2]] the answer is [3, 3, 2, 1]. Describe what changes, then write it if you like.
Compare with our answer
The same union-find already tracks the count as it goes, so record it after every edge instead of returning it once at the end.
def counts_after_each(n, edges):
parent = list(range(n))
def find(x):
while parent[x] != x:
parent[x] = parent[parent[x]]
x = parent[x]
return x
groups, out = n, []
for a, b in edges:
ra, rb = find(a), find(b)
if ra != rb:
parent[rb] = ra
groups -= 1
out.append(groups)
return out
Time O(V + E log V), space O(V + E) for the output. A repeated edge leaves the count unchanged.
A strong answer mentions: appending the count after every edge, that union-find handles edges arriving online, and that a full search per edge would cost O(E·(V + E)).
1. Friend requests arrive one at a time among 10^5 users. After each request you must report how many friend circles exist. Which approach fits best?
Union-find merges two groups in near-constant time and updates the count as requests arrive. A full DFS per request repeats O(V + E) work each time, and Kahn's algorithm applies to directed graphs.
2. Why does the shown code start with groups = n?
With no edges every node is a separate group. Each successful merge then reduces the count by one. The value is the number of groups, not the largest size or an edge bound.
3. A learner replaces parent[rb] = ra with parent[b] = a. Which input now returns a wrong count?
The second edge overwrites the link of node 0 and detaches node 1 from the group, so the third edge looks like a new merge and the count drops to 0. The other inputs never overwrite the parent of a node that already has one.
Score 60% or more and the lesson is marked complete.