Number of Connected Components in an Undirected Graph
MediumGraphs
You get n nodes, numbered 0 to n - 1, and a list of undirected edges, where [a, b] joins node a and node b.
Return how many connected components the graph has: groups of nodes that can reach each other along the edges. A node with no edges is a component of its own.
Examples
Input: n = 6, edges = [[0, 1], [1, 2], [3, 4]] Output: 3
The groups are {0, 1, 2}, {3, 4} and {5} on its own.
Input: n = 4, edges = [[0, 1], [1, 2], [2, 3], [3, 0]] Output: 1
The four edges make one ring through every node.
Constraints
1 ≤ n ≤ 20000 ≤ edges.length ≤ 50000 ≤ a, b < nanda ≠ b- No edge appears twice.
Stuck?
Hint 1
Start with n separate groups. Every edge that joins two different groups merges them into one.
Hint 2
Use union-find: find the root of each end, and when the roots differ, link one root to the other and subtract one from the count. Linking the nodes themselves instead of their roots loses groups.
The idea
Start with every node in a group of its own, which makes n groups. An edge between two different groups merges them into one, and an edge inside a group changes nothing. Union-find tells those two cases apart quickly.
Time O(n + e · log n) for e edgesExtra space O(n)
Try it again with the idea in mind, or go through the code one step at a time.
The code, step by step
Step 1 of 6
Union-find: each node starts as the root of its own group.
function countComponents(n, edges) { const parent = Array.from({ length: n }, (_, i) => i); const find = (x) => { while (parent[x] !== x) { parent[x] = parent[parent[x]]; x = parent[x]; } return x; }; let count = n; for (const [a, b] of edges) { const rootA = find(a); const rootB = find(b); if (rootA !== rootB) { parent[rootA] = rootB; count--; } } return count;}The trap
This version links the second end of each edge to the first, parent[b] = a, then counts the nodes that are still their own parent. On a chain listed in order it gets the right count. But when a node is the second end of two edges, the second link overwrites the first, and a node the first edge had joined is left as a root of its own. Linking the roots that find returns keeps every earlier link.
function countComponents(n, edges) { const parent = Array.from({ length: n }, (_, i) => i); for (const [a, b] of edges) parent[b] = a; // links the nodes, not their roots, so earlier links are lost let count = 0; for (let i = 0; i < n; i++) if (parent[i] === i) count++; return count;}