Graphs · LC #323
Number of Connected Components in an Undirected Graph
Count connected components in an undirected graph using Union-Find - start with n components, decrement each time two previously separate nodes are merged.
Statement
Problem & Approach
Problem statement, sample I/O, and key reasoning.
You have a graph of `n` nodes labeled from `0` to `n - 1`. You are given an integer `n` and a list of `edges` where `edges[i] = [ai, bi]` indicates an undirected edge between nodes `ai` and `bi`. Return the number of connected components in the graph.
Sample I/O
Input: n=5, edges=[[0,1],[1,2],[3,4]] Output: 2 Input: n=5, edges=[[0,1],[1,2],[2,3],[3,4]] Output: 1
Intuition
How to Think About It
Intuition
Start with n separate components (each node is its own component). For each edge, union the two endpoints. If they were in different components, one component disappears - decrement count. Final count is the number of components remaining.
Core Concept
Union-Find (DSU). Initialize parent[i] = i, count = n. For each edge (a, b): pa = find(a), pb = find(b). If pa != pb: parent[pa] = pb, count--. Path compression in find() keeps operations near O(1) amortized.
When to use
Counting connected components dynamically as edges arrive; any problem requiring incremental connectivity tracking; Kruskal's MST; redundant edge detection.
When NOT to use
When component membership must be queried after edge deletions (DSU doesn't support deletion efficiently). When the graph is directed (DFS/BFS with state needed). When you need the actual component members, not just the count.
Key Insights
What to Know Cold
- Initializing count = n and decrementing on successful union is elegant - avoids post-processing to count roots.
- Path compression (parent[x] = parent[parent[x]] or full flattening) is the key optimization.
- Union by rank prevents DSU trees from becoming linked lists, bounding tree height to O(log n).
- DFS/BFS alternative: mark visited, count DFS launches from unvisited nodes - same O(V+E) complexity.
- This is the canonical Union-Find problem; mastering it unlocks Redundant Connection, Accounts Merge, etc.
1 example
Worked Examples
Union-Find component counting
n=5, edges=[[0,1],[1,2],[3,4]] - two separate clusters.
Init count=5; union each edge; decrement count on successful union; return count.
function countComponents(n: number, edges: number[][]): number {
const parent = Array.from({ length: n }, (_, i) => i);
const find = (x: number): number => {
while (parent[x] !== x) { parent[x] = parent[parent[x]]; x = parent[x]; }
return x;
};
let count = n;
for (const [a, b] of edges) {
const pa = find(a), pb = find(b);
if (pa !== pb) { parent[pa] = pb; count--; }
}
return count;
}Output: 2
Canonical Union-Find problem. Interviewers use it to verify DSU fundamentals before harder problems like Redundant Connection or Accounts Merge.