Keep track of who belongs to which group as groups keep merging — friend networks, connected components, Kruskal’s spanning trees — answering “same group?” in almost constant time. The whole structure is one array of parent pointers, so it runs in real I-13 now. Its famous optimization even bumps into the campaign’s newest wall.
THE TECHNIQUE each element points at a parent; roots name the set
Find follows parents to the root (the set’s name). Union points one root at the other, merging two sets into one. Click two nodes to union them; nodes in the same set share a colour. live demo
HISTORY & CREDIT a structure whose speed took a decade to prove
Simple to write, but its true cost was a quick homework problem — it took one of the great theorists to pin it down. cited
1964 · Bernard Galler & Michael Fischer describe the parent-array structure (for a FORTRAN equivalence problem). the tricks · union by rank (hang the shorter tree under the taller) and path compression (on the way to a root, point everything straight at it) make operations almost free. 1975 · Robert Tarjan proves the total cost of m operations is O(m · α(n)), where α is the inverse Ackermann function — effectively a small constant (≤ 4 for any n in the universe). A famously tight, hard-won bound.
The data structure is trivial; the theorem about it is a landmark. deep
RECOMMEND FOR I-13 runs — and its optimization finds the new wall
The structure is a single parent array. Find, union, and connectivity all run on it:
def find(I p, I x) { I px <- p[x] if px == x { -> x } -> find(p, px) }
def uni(I p, I a, I b) { p[find(p,a)] <- find(p,b) -> p }
$ i13 run uf.i13 # union 0-1, 2-3, 1-3
c02 = 1 # 0 and 2 now share a set
c05 = 0 # 0 and 5 do not
Recommend: basic union-find is a no-wall on the new array. But its key speedup, path compression, wants find to return both the root and the rewired array — two values — and an I-13 function returns one. That is the exact wall quicksort (dart 045) hit: multiple return. A second independent dart lands on it, which is the campaign’s signal that it is real. The tally of open recommends:multiple return (darts 045, 048) and bignum (032/035/041/047). Two frontiers, each now named by more than one dart.