THE UNION-FIND — a dart

UNION-FIND a structure that flattens itself as you ask — near-constant-time connectivity

Union-find (disjoint-set) answers “are these two things connected?” over a stream of merges, using a parent array where each element points toward a representative root. Two optimizations make it astonishing: union by rank attaches the smaller tree under the larger, and path compression re-points every node to the root as you traverse it — so the structure flattens itself with use. Together they give an amortized cost of the inverse Ackermann function, effectively constant — a query makes future queries faster. It is the engine of Kruskal’s MST, connected components, and cycle detection. Connect {0-1, 2-3, 1-3} and 0..3 collapse into one set; 4 stands alone — 2 components.

THE TECHNIQUE parent array; find + union-by-rank + path compression — ~O(α(n))

The demo unions {0-1, 2-3, 1-3} — 0 and 3 become connected, and five singletons collapse to 2 components: live demo

HISTORY & CREDIT Galler & Fischer 1964 · Tarjan 1975

“Connectivity queries get slower as you add merges.” — path compression flattens the structure with use, so queries stay near-constant. cited

the array · each element points at its parent; a root points at itself — find follows to the root.
the flattening · path compression re-points nodes to the root during find — the structure self-optimizes.
1964 / 1975 · Galler & Fischer; Tarjan proved the inverse-Ackermann bound.

A structure that gets faster the more you query it, folding its own paths flat — connectivity at near-constant cost. self-flattening

RECOMMEND FOR I-13 the merged sets, on the compiler

On the canonical compiler, unioning {0-1, 2-3, 1-3} connects 0 and 3 and leaves 2 components (the merged {0,1,2,3} and the singleton 4):

$ i13 run nw_unionfind.i13 # find + union on a parent array RUN OK · 418 step(s) · peak stack 8 · call depth 6 connected_0_3 = 1 -- 0 and 3 share a root components = 2 -- {0,1,2,3} and {4}

Recommend as the batch’s keeper shot, then NULL. Path compression is genuinely striking — the structure rewrites itself as you read it, which tempts a “self-optimizing representation” axis. But two union-finds, one with compression and one without, compute the same connectivity (the roots are the same sets); they differ only in internal shape and amortized cost — the resource axis (B40). The compression is an optimization of the representation (B44), not a change to the answer. NULL — but the loveliest structure in the batch: a data structure that flattens with use.