Union-find (disjoint sets)
Track which items are connected under repeated merges, in nearly constant time per operation.
Number of Connected Components. Given n nodes labelled 0..n-1 and a list of undirected edges, return how many connected components there are.
Signals that point here
- Edges arrive one at a time and you need connectivity after each (dynamic connectivity).
- "Are these two in the same group?", accounts merge, friend circles, redundant connection.
- Kruskal's minimum spanning tree.
The idea
Each component is a tree; parent[x] points toward its root, and two nodes are connected exactly when they have the same root. Union points one root at the other.
Two optimisations make it fast: path compression (here the halving form, parent[x] = parent[parent[x]]) and union by rank or size. With both, a sequence of m operations costs O(m·α(n)), where α is the inverse Ackermann function: effectively constant. This version uses compression only, which is usually enough in an interview; say what rank would add.
BFS or DFS also count components in O(n + e). Prefer union-find when edges stream in or when you need repeated connectivity queries.
def count_components(n: int, edges: list[list[int]]) -> int:
parent = list(range(n))
def find(x: int) -> int:
while parent[x] != x:
parent[x] = parent[parent[x]] # path halving
x = parent[x]
return x
components = n
for a, b in edges:
ra, rb = find(a), find(b)
if ra != rb:
parent[ra] = rb
components -= 1
return componentspublic static class UnionFind
{
public static int CountComponents(int n, int[][] edges)
{
var parent = Enumerable.Range(0, n).ToArray();
int Find(int x)
{
while (parent[x] != x)
{
parent[x] = parent[parent[x]]; // path halving
x = parent[x];
}
return x;
}
int components = n;
foreach (var e in edges)
{
int ra = Find(e[0]), rb = Find(e[1]);
if (ra != rb) { parent[ra] = rb; components--; }
}
return components;
}
}Complexity
With path compression alone, amortised O(log n) per operation; with union by rank as well, O(α(n)). O(n) space.
Pitfalls interviewers watch for
- Unioning
aandbthemselves instead of their roots. - Decrementing the component count on every edge, including ones inside a component.
- Recursive
findin Python on a long chain: the recursion limit. The iterative form avoids it.
Variants worth knowing
- Redundant connection: the first edge whose endpoints already share a root.
- Accounts merge: union e-mails that appear in the same account, then group by root.
- Kruskal: sort edges by weight, add an edge when it joins two different roots.
Test it like the interviewer will
count_components(5, [[0, 1], [1, 2], [3, 4]])returns2count_components(5, [[0, 1], [1, 2], [2, 3], [3, 4]])returns1count_components(4, [])returns4count_components(3, [[0, 1], [1, 0], [0, 1]])returns2- Say the cases out loud before you run them. OpenAI's published guide names test coverage as part of the bar; see Sources.
Step through it: count_components(6, [[0, 1], [2, 3], [1, 2], [4, 5], [0, 3]])
Each step is recorded from an instrumented copy of the Python above, run when the site was built.
Practice
Written for this site to drill the lesson. Not reported interview questions.
- Return the edge that, when removed, turns a graph back into a tree.
- Merge user accounts that share any e-mail address.
- Count islands in a grid where land cells are added one at a time, reporting the count after each.
Check yourself
When do two nodes belong to the same component?
When find returns the same root for both.
What do path compression and union by rank give you together?
Amortised O(α(n)) per operation.