Union–Find

The problem it solves

A stream of “these two are connected” facts arrives — friendships forming, network cables plugged in, pixels adjacent in a blob — and between facts you must answer “are X and Y in the same group?” instantly. Rebuilding groups from scratch per query is ruinous; running a fresh DFS per question is O(V + E) each time. Union–Find (the disjoint set union, DSU) maintains the groups incrementally: merging two groups and asking “same group?” each cost effectively constant time, forever, no matter how tangled the history.

Its headline clients: Kruskal’s minimum spanning tree (sort edges, take each unless it closes a cycle — the cycle check is union-find), accounts-merge and friend-circle problems, image segmentation, percolation physics, and the online form of “number of connected components”. The tell in a problem statement is incremental connectivity: edges arrive over time, queries interleave.

The intuition — and where it breaks down

Merging companies. Every company has a CEO; every employee, asked “who’s ultimately in charge?”, walks up their reporting chain to the top. Two employees work for the same company exactly when their chains end at the same CEO. A merger is one email: CEO of company A now reports to CEO of company B. Nobody else changes anything — thousands of employees are re-parented implicitly, because their chains now continue one hop further.

That laziness is the entire efficiency story, and also its threat: careless mergers build reporting chains a thousand links long, and “walk to the top” stops being cheap. Two fixes, both one line. Path compression: whenever an employee walks the chain, re-point them (and everyone en route) directly at the CEO — the walk pays for flattening. Union by rank/size: in a merger, the shallower hierarchy reports to the deeper one, so chains grow only when merging equals. Either alone gives O(log n) amortized; together, the inverse-Ackermann bound — constant for any input that fits in this universe.

Where the analogy breaks: real orgs have meaningful middle managers; DSU’s internal structure means nothing — only the root identifies the set, and path compression gleefully destroys all internal shape. Also, real mergers can unwind. DSU cannot un-merge: the structure only coarsens. Deletion needs offline trickery (process time backwards, so deletions become insertions) or a different structure entirely — a follow-up interviewers keep loaded.

Loading…

A walkthrough you can check

Nodes A–F, edges arriving: A–B, C–D, B–C, A–D, E–F.

1. A–B: find(A)=A, find(B)=B — different roots. Union. Components: 6 → 5.
2. C–D: different roots. Union. 5 → 4.
3. B–C: find(B) walks to A’s root; find(C) to C-or-D’s root. Different — union. The merged blob {A,B,C,D} now shares one root. 4 → 3.
4. A–D: find(A) and find(D) both answer the same root. This edge adds nothing — it would close a cycle. Rejected, count unchanged. This rejection is Kruskal’s entire cycle test.
5. E–F: union. 3 → 2. Final: two components, {A,B,C,D} and {E,F}.

The arithmetic worth internalizing: every union drops the component count by exactly one, never more — so n nodes reach k components after exactly n − k successful unions, and the number of rejected edges is pure cycle content. The visualization labels every node with its current root and asks, per edge, “merge or cycle?” — the answer is always just “same root or not”.

The invariant

Each node’s parent chain terminates at its set’s root, and two nodes share a set iff they share a root. Everything else — compression, rank — preserves this while shortening chains. The operational corollary that catches most bugs: only roots may be compared, and only roots may be merged. Comparing parent[x] values, or setting parent[x] = y instead of parent[find(x)] = find(y), silently splits sets.

Second invariant, for union-by-size: a root’s recorded size is its true set size. It powers the “smaller under larger” rule and gives free answers to “how big is X’s group?” — a variant question that costs nothing if the bookkeeping was kept.

Complexity, derived

Space: one parent array, one rank/size array — O(n). Time: find costs the chain length; union is two finds plus one pointer write. With union-by-rank alone, chains are bounded by log n (a rank-r root commands ≥ 2^r nodes — provable by induction on merges of equals). Adding compression, the amortized cost per operation drops to α(n), the inverse Ackermann function — ≤ 4 for n below astronomical, so “effectively constant” is not hand-waving but a theorem (Tarjan’s, and its lower-bound twin says you can’t do better). For interviews: say α honestly, then say “constant in practice”, in that order.

The comparison that frames when to use it: a static, fully-known graph’s components fall to one DFS/BFS in O(V + E) with less machinery. DSU wins when edges arrive online, when queries interleave with merges, or inside Kruskal where edges arrive in sorted order by design.

What people get wrong

Writing find without compression and shipping it. Correct, and O(n) per query on chain-shaped inputs — the difference between passing and timing out on large tests. Compression is one line (parent[x] = find(parent[x]) in the recursive form); its absence is the most common DSU performance bug.

Compression without the rank rule (or vice versa) and claiming α. Each alone is O(log n) amortized. The α bound needs both. Precision here is cheap and noticed.

Forgetting roots can change identity. After union(a, b), yesterday’s root of a’s set may now be an internal node. Caching roots across unions is a stale-pointer bug wearing a disguise.

Treating the parent array as the answer. The parent structure is scaffolding; queries must go through find. Printing parent[x] as “x’s group” is wrong the moment any chain has length ≥ 2.

Implementation notes across languages

The structure is two arrays and portable everywhere; the notes are about form. Python: the recursive find with compression is elegant but recursion-limited on adversarial chains — the iterative two-pass (walk to root, walk again re-pointing) or path-halving (parent[x] = parent[parent[x]] while walking, used in this visualization) avoids the limit with equal asymptotics. Java/C++: index-based arrays make this one of the fastest structures in existence — competitive programmers reach for DSU precisely because its constant factors are tiny. JavaScript: plain arrays, same story; use numeric ids, not object keys. Cross-language: initialize parent[i] = i (everyone their own CEO), and if the problem’s nodes are strings, intern them to indices first — a Map-backed DSU is measurably slower and no clearer.