Number of Connected Components in an Undirected Graph
Problem
n nodes labelled 0..n-1 and a list of undirected
edges, where [a, b] joins nodes a and b.
Return how many connected components the graph has — i.e. how many separate
“islands” of nodes remain, counting isolated nodes as their own island.n=5, edges=[[0,1],[1,2],[3,4]]Output2n=5, edges=[[0,1],[1,2],[2,3],[3,4]]Output1n=4, edges=[]Output41 ≤ n ≤ 2000 · 0 ≤ edges.length ≤ 5000 · a ≠ b · no repeated edges
Try it yourself
class Solution {
public int countComponents(int n, int[][] edges) {
}
}
n minus the number of
successful merges — exactly what Union-Find counts.Instinct Items get grouped by "connected", "same as" or "shares a" links and you keep asking which group something is in: merge sets with Union-Find.
Memory hack Find your boss, merge the bosses; squash the chain (path compression) and hang the short tree under the tall one (rank).
Open the Union-Find guide →Approaches
Brute ForceLabel Propagation Until Stable
O(V · E)Space O(V)Give every node its own label. Repeatedly sweep the edge list and let both ends
adopt the smaller label. The minimum label spreads one hop per sweep, so after at most
V sweeps every component carries its smallest node id; count nodes whose
label is still their own id.
public int countComponents(int n, int[][] edges) { int[] label = new int[n]; for (int i = 0; i < n; i++) label[i] = i; boolean changed = true; while (changed) { changed = false; for (int[] e : edges) { int m = Math.min(label[e[0]], label[e[1]]); if (label[e[0]] != m || label[e[1]] != m) { label[e[0]] = m; label[e[1]] = m; changed = true; } } } // Each component ends up labelled with its smallest node id int count = 0; for (int i = 0; i < n; i++) if (label[i] == i) count++; return count; }
No graph structure needed, but up to V full passes over the edges.
BetterAdjacency List + DFS Flood Fill
O(V + E)Space O(V + E)Build an adjacency list. Scan nodes; each unvisited node starts a new component, and an iterative DFS marks everything reachable from it. Every node and edge is touched a constant number of times.
public int countComponents(int n, int[][] edges) { List<List<Integer>> adj = new ArrayList<>(); for (int i = 0; i < n; i++) adj.add(new ArrayList<>()); for (int[] e : edges) { adj.get(e[0]).add(e[1]); adj.get(e[1]).add(e[0]); } boolean[] seen = new boolean[n]; int count = 0; Deque<Integer> stack = new ArrayDeque<>(); for (int s = 0; s < n; s++) { if (seen[s]) continue; count++; // new island found seen[s] = true; stack.push(s); while (!stack.isEmpty()) { int u = stack.pop(); for (int v : adj.get(u)) { if (!seen[v]) { seen[v] = true; stack.push(v); } } } } return count; }
Linear time, but must materialise the whole adjacency list first.
OptimalUnion-Find (Path Compression + Union by Size)
O(V + E · α(V))Space O(V)Keep a parent array where each component has one root. For every edge find both roots; if they differ, link the smaller tree under the larger and decrement the component count. Path compression keeps trees almost flat, so each operation is effectively constant.
private int[] parent, size; public int countComponents(int n, int[][] edges) { parent = new int[n]; size = new int[n]; for (int i = 0; i < n; i++) { parent[i] = i; size[i] = 1; } int components = n; for (int[] e : edges) { if (union(e[0], e[1])) components--; } return components; } private int find(int x) { while (parent[x] != x) { parent[x] = parent[parent[x]]; // path halving x = parent[x]; } return x; } private boolean union(int a, int b) { int ra = find(a), rb = find(b); if (ra == rb) return false; // already connected if (size[ra] < size[rb]) { int t = ra; ra = rb; rb = t; } parent[rb] = ra; size[ra] += size[rb]; return true; }
Near-linear, only O(V) memory, and works when edges arrive as a stream.
At a glance
| Level | Approach | Time | Space |
|---|---|---|---|
| Brute Force | Label Propagation Until Stable | O(V · E) | O(V) |
| Better | Adjacency List + DFS Flood Fill | O(V + E) | O(V + E) |
| Optimal | Union-Find (Path Compression + Union by Size) | O(V + E · α(V)) | O(V) |
- Forgetting isolated nodes — a node with no edges is still one component.
- Decrementing the count on every edge — edges that close a cycle must not count.
- Adding only one direction to the adjacency list — the graph is undirected.
- Mention both DFS and Union-Find; pick Union-Find if edges could arrive incrementally.
- Explain why path compression + union by size gives near-constant amortised cost.
- Use an iterative stack for DFS to avoid deep recursion on a long chain.