Number of Connected Components — Union-Find Tracking
Initialise each node in its own set and union edges; the remaining number of roots equals the connected components.
Problem Statement
Given n nodes labeled 0..n-1 and a list of undirected edges, return the number of connected components.
Why This Problem Matters
- Union-find is an essential tool for connectivity questions.
- Encourages discussion around path compression and union by rank.
- Generalises to many MST and clustering problems.
Thought Process
Start with each node isolated
Initially component count equals n; unions decrease the count when they connect separate sets.
Union edges efficiently
For each edge (u, v), find their roots; if different, union them and decrement count.
Use path compression
Path compression ensures near-constant time finds, keeping the solution fast.
Step-by-Step Reasoning
- Initialise parent[i] = i and rank[i] = 1.
- Set components = n.
- For each edge, union endpoints if their roots differ, decrementing components.
- Return components.
Dry Run
n = 5, edges = [[0,1],[1,2],[3,4]]
After unions, components = 2.
n = 5, edges = []
No unions; components remain 5.
Complexity Analysis
Time
O(n α(n))
Space
O(n)
Why
Inverse Ackermann function α(n) is effectively constant in practice.
Annotated Solution
public class NumberOfConnectedComponents {
public int countComponents(int n, int[][] edges) {
UnionFind uf = new UnionFind(n);
int components = n;
for (int[] edge : edges) {
if (uf.union(edge[0], edge[1])) {
components -= 1;
}
}
return components;
}
private static class UnionFind {
private final int[] parent;
private final int[] rank;
UnionFind(int size) {
parent = new int[size];
rank = new int[size];
for (int i = 0; i < size; i += 1) {
parent[i] = i;
rank[i] = 1;
}
}
int find(int x) {
if (parent[x] != x) {
parent[x] = find(parent[x]);
}
return parent[x];
}
boolean union(int a, int b) {
int rootA = find(a);
int rootB = find(b);
if (rootA == rootB) {
return false;
}
if (rank[rootA] < rank[rootB]) {
parent[rootA] = rootB;
} else if (rank[rootA] > rank[rootB]) {
parent[rootB] = rootA;
} else {
parent[rootB] = rootA;
rank[rootA] += 1;
}
return true;
}
}
}Union by rank keeps trees shallow, and find with path compression ensures almost constant time per operation.
Common Pitfalls
- Neglecting to decrement components when a union occurs leaves the count inflated.
- Implementing union without rank may cause trees to degrade and slow finds.
- Off-by-one errors when nodes are labeled from 1..n require careful indexing.
Follow-Up Questions
- How would you implement this with DFS instead?
- Can you track the size of each component while unioning?