function connectedComponents(graph: Graph) {const parent = new Map(graph.nodes.map((node) => [node, node]));
const find = (node: Node): Node => (parent.get(node) === node ? node : (parent.set(node, find(parent.get(node)!)), parent.get(node)!));
for (const edge of graph.edges) {const rootA = find(edge.from), rootB = find(edge.to);
if (rootA === rootB) continue;
parent.set(rootA, rootB);
}
return new Set(graph.nodes.map(find)).size;
}
Every node starts as its own set; the label is its representative. Edges arrive in a shuffled order, as if streamed.
Understanding Union-Find
The idea
Union-find keeps a forest: every node points at a parent, and the root of its tree is the representative of its set. Find follows the pointers to the root; union makes one root point at the other. Two nodes are connected exactly when their finds return the same root.
Two tricks make it almost free. Path compression makes every node visited by a find point straight at the root afterwards, and union by rank keeps trees shallow. With both, a sequence of m operations costs O(m · α(n)), where α is the inverse Ackermann function, below 5 for any input that fits in the universe.
The four stages
Complexity
Versus its siblings
Pseudocode
UNIONFIND(graph)
parent[node] ← node for every node
FIND(node): follow parent pointers to the root, then point every node on the way straight at it
for each edge from–to: if FIND(from) ≠ FIND(to): parent[FIND(from)] ← FIND(to)
the components are the distinct roots
When to use
Pitfalls
History
Bernard Galler and Michael Fischer described the forest representation in 1964. Robert Tarjan proved the inverse-Ackermann bound in 1975 and, with Jan van Leeuwen in 1984, showed that no pointer-based structure can do better, one of the few tight amortised results in the field.