Disjoint-Set Union-Find

A disjoint-set forest represents each set as a rooted tree where every element points to a parent, and the root of the tree is the set's designated representative. Two elements belong to the same set exactly when following parent pointers from each of them leads to the same root. This is the key structural idea: instead of storing explicit set membership lists, union-find encodes set membership implicitly through tree structure, using only one array of parent pointers. Two elements `x` and `y` are in the same set if and only if `Find(x) = Find(y)`, where `Find` walks up parent pointers until it reaches a node that is its own parent (the root). `Union(x, y)` merges the two sets by first finding the roots of `x` and `y`, and if they differ, making one root point to the other. Initially, in `MakeSet(x)`, every element is its own singleton set — its own root. The naive version of this idea is correct but slow: repeated unions can build a long chain (a degenerate tree resembling a linked list), making `Find` take `O(n)` time in the worst case. The fix comes from two complementary heuristics. Union by rank (or the closely related union by size) keeps trees shallow by always attaching the root of the smaller-ranked tree beneath the root of the larger-ranked tree, preventing the accidental construction of long chains. Path compression goes further: every time `Find` walks a path to the root, it rewires every visited node to point directly at the root, so subsequent queries on those nodes are instant. Neither optimization alone gives the best bound; together, they yield the celebrated near-constant amortized time per operation, expressed using the inverse Ackermann function `α(n)`.

The structure keeps two arrays indexed by element: `parent[x]`, the parent pointer, and `rank[x]`, an upper bound on the height of the subtree rooted at `x` (used only to guide unions, not maintained as an exact height once path compression starts firing).

`MakeSet(x)` initializes `x` as its own singleton set: `parent[x] = x`, `rank[x] = 0`.

`Find(x)` walks parent pointers to the root, then compresses the path so every node on it points directly to the root. This is most cleanly written recursively: ``` FIND(x): if parent[x] != x: parent[x] = FIND(parent[x]) // path compression return parent[x] ``` An equivalent, stack-free iterative version first walks to the root, then walks again to relink: ``` FIND-ITER(x): root = x while parent[root] != root: root = parent[root] // second pass: path compression while parent[x] != root: next = parent[x] parent[x] = root x = next return root ```

`Union(x, y)` finds the two roots and, if they differ, attaches the shorter tree under the taller one, using `rank` as the tie-breaking guide: ``` UNION(x, y): rx = FIND(x) ry = FIND(y) if rx == ry: return // already in the same set if rank[rx] < rank[ry]: swap(rx, ry) parent[ry] = rx // attach shorter/equal-rank tree under taller if rank[rx] == rank[ry]: rank[rx] = rank[rx] + 1 ```

`Connected(x, y)` is simply `FIND(x) == FIND(y)`. The full pseudocode for building a disjoint-set structure over `n` elements and processing a sequence of operations: ``` MAKE-SET(x): parent[x] = x rank[x] = 0 INITIALIZE(n): for x = 1 to n: MAKE-SET(x) ``` A subtle but important detail: `rank[x]` is only ever incremented when two trees of equal rank are merged (the tie-break case). This guarantees rank behaves like an upper bound on tree height even though path compression can make actual heights shrink below the stored rank. Because rank never decreases, the invariant "a tree rooted at `x` with rank `r` has at least `2^r` nodes" (proved below) is preserved throughout the algorithm's execution, and this is precisely what bounds the tree heights logarithmically even before path compression is added.

Correctness. The core invariant is: at every point in the execution, the disjoint-set forest partitions the universe into trees, and two elements are in the same set if and only if they have the same root. This holds by induction on the operation sequence. `MakeSet(x)` trivially creates a singleton tree rooted at `x`. `Find(x)` never changes which tree any node belongs to — it only shortcuts pointers within the same tree, since every relinked node still ultimately points to the same root it pointed to before. `Union(x, y)` only changes the tree structure by attaching one entire root (and hence its whole tree) under another root; this merges exactly the two sets containing `x` and `y`, without touching any other tree. Hence the partition into sets, defined by "same root", is preserved correctly across arbitrary sequences of operations, and set membership queries via `Find` equality are always accurate.

Why union by rank keeps trees shallow. Define the rank of a root as the length of the longest root-to-leaf path at the time it was assigned as a non-root under the rule "rank only increases when merging equal-rank trees." One can prove by induction that a tree rooted at a node of rank `r` contains at least `2^r` nodes. Base case: rank `0` trees are singletons, `2^0 = 1` node. Inductive step: a tree of rank `r+1` is formed only by merging two trees of rank `r`, each with at least `2^r` nodes, giving at least `2^{r+1}` nodes. Since ranks are bounded by `log n` (because `2^r ≤ n`), tree height is `O(log n)` using union by rank alone, even without path compression. This already gives `O(log n)` per operation.

Why path compression alone helps, and why together they are better still. Path compression flattens trees on every find, so repeated queries on the same elements become cheap. Used alone (with naive union), a sequence of `m` operations costs `O(m log n)` amortized. The real payoff appears when both optimizations are combined: a classical result, first analyzed rigorously by Tarjan, shows that a sequence of `m` union/find operations on `n` elements takes ``` O(m · α(n)) ``` total time, where `α(n)` is the inverse Ackermann function — the functional inverse of the extraordinarily fast-growing Ackermann function. `α(n)` grows so slowly that `α(n) ≤ 4` for any `n` up to numbers vastly larger than the number of atoms in the observable universe. For every practical input size, `α(n)` is a small constant (at most 4 or 5), so the amortized cost per operation is, in effect, `O(1)`.

Proof sketch of the bound (potential-function argument). The standard proof assigns each node a level based on how large its subtree's rank gap is relative to a tower-of-twos function, and bounds the number of times a node can jump levels due to path compression across the whole operation sequence. Nodes are partitioned into `O(α(n))` groups by rank ranges growing as fast as the Ackermann hierarchy; a node's parent pointer can be "compressed past" a boundary of its group only once per group, because rank is monotonically increasing along any root path and never decreases. Summing the bounded number of expensive per-node compressions across all `n` nodes and adding the `O(1)` work per operation for cheap steps yields the `O(m α(n))` total — the details require careful bookkeeping but the intuition is: each node can only be "compressed away from its group" a bounded number of times before it never needs compressing again relative to that scale, and there are only `α(n)` scales to exhaust.

Space complexity. Two arrays of size `n` (`parent`, `rank`), so `O(n)` space — no auxiliary structures needed.

Honest tradeoffs. Union-find does not support splitting a set back apart (no efficient `Delete` or `Split`), does not preserve insertion order or enumerate a set's members efficiently without extra bookkeeping (e.g., an auxiliary linked list per set for that purpose), and offers no way to recover the original tree shape once compressed — it is a pure query structure for connectivity, not a general graph structure. If arbitrary set splitting is required, other structures (like a fully dynamic connectivity structure with link-cut trees) are needed instead, at higher cost.

Trace `Union` and `Find` over elements `{1,...,8}` with union by rank and path compression, processing the operations in order.

After step 9, every element's parent points directly at `1` except where the tree structure already had direct children of `1` (namely `2`, `3`, `5`, and now `4`, `7`, `8`). The single tree is now of height at most 2, down from a height-3 tree before compression — subsequent `Find` calls on any of `2..8` are single hops. Trace `Find(8)` step by step to make the compression mechanics explicit: ``` FIND(8): parent[8] = 7 ≠ 8, so recurse: FIND(7) parent[7] = 5 ≠ 7, so recurse: FIND(5) parent[5] = 1 ≠ 5, so recurse: FIND(1) parent[1] = 1 → base case, return 1 parent[5] = 1 (unchanged, already correct) return 1 parent[7] = 1 (compressed from 5 to 1) return 1 parent[8] = 1 (compressed from 7 to 1) return 1 ``` This confirms the table: the recursive unwind rewrites `parent[7]` and `parent[8]` to point straight to the true root `1`, while `parent[5]` needed no change since it already pointed at `1`.

The disjoint-set forest with union by rank and path compression is one of the cleanest success stories in algorithm design: two simple local rules combine to defeat what looks like an unavoidable logarithmic — or even linear — cost, and the proof that they do so requires genuinely deep combinatorial analysis connecting data structures to the Ackermann function, a connection that surprised the field.

Union-find is embedded in the machinery of many production systems and classical algorithms. Kruskal's minimum spanning tree algorithm relies on union-find to detect, in near-constant time, whether adding an edge would create a cycle — sorting edges by weight and using `Find` to check components is what makes Kruskal's algorithm run in `O(E log E)` dominated by the sort, not the connectivity checks. Cycle detection in undirected graphs, generally, uses the same idea: process edges, and if both endpoints are already in the same set, a cycle exists. In compilers and type systems, union-find implements efficient unification for type inference (as in Hindley-Milner style algorithms), where type variables are merged as constraints are discovered. In computer vision, connected-component labeling in binary images uses union-find to merge pixel labels across scan lines in a single pass. In network and social-graph analytics, streaming connectivity queries — "are these two nodes in the same connected component after this batch of edge insertions?" — are answered with union-find when only insertions (not deletions) occur, which is the common case for "add friend," "merge accounts," or "add link" style event streams. It also underlies percolation simulations in statistical physics and least common ancestor offline algorithms (Tarjan's off-line LCA algorithm reuses the same forest). Anywhere a system incrementally merges group memberships and must repeatedly test group equality, this structure — building on ideas from Arrays and Dynamic Arrays for its backing storage and echoing tree-traversal patterns familiar from Stacks-based iterative traversal — is the default and near-optimal tool, closely related in spirit to broader techniques in Amortized Analysis used throughout data structure design.

Ask the tutor: Can you show how union-find's amortized bound is proved using a potential-function argument over rank-based groupings, in full detail?