# union–find Union–find, or the disjoint-set union structure, maintains a partition of a fixed universe into non-overlapping sets. It answers one question extremely well: *are these two elements connected by the unions observed so far?* Its interface has three operations: - `makeSet(x)` creates the singleton set `{x}`; - `find(x)` returns a representative for the set containing `x`; - `union(a, b)` merges the two sets when their representatives differ. Representatives are implementation identities, not meaningful members chosen by the caller. Equality of representatives is what proves connectivity. ## a forest, flattened by use The standard representation is a forest of parent pointers. Every set is one tree; its root is the representative and points to itself, or stores a special root marker. `find` follows parents to a root. `union` changes one root's parent to the other root.

Path compression rewrites every parent followed by a find to point at the representative. The partition is unchanged; only its internal shape improves.

A compact parent array often stores roots as negative set sizes: ```text parent[x] >= 0 → parent index parent[x] < 0 → x is a root; -parent[x] is the set size ``` This combines parent pointers and rank metadata in one machine word per element. It requires elements to have dense integer identifiers, or a separate map from external keys to those identifiers. ## weighted union A naive union can repeatedly attach a large tree beneath a singleton and create a linear chain. **Union by size** attaches the smaller root beneath the larger; **union by rank** attaches the shallower tree beneath the deeper one and raises the rank only when equal ranks meet. ```text union(a, b): ra = find(a) rb = find(b) if ra == rb: return false if size[ra] < size[rb]: swap(ra, rb) parent[rb] = ra size[ra] += size[rb] return true ``` Without path compression, weighted union keeps tree height logarithmic. With path compression, each successful or unsuccessful query also makes future queries cheaper. ## path compression A full compression find first locates the root, then walks the path again and rewrites every parent: ```text find(x): root = x while parent[root] is not a root: root = parent[root] while x != root: next = parent[x] parent[x] = root x = next return root ``` Two one-pass relatives are common: - **path splitting** makes every visited node point to its grandparent; - **path halving** does this for every other node. They can have simpler loops and excellent practical behavior. All preserve the same partition. ## complexity A sequence of `m` operations on `n` elements using weighted union and path compression costs ```text O(m α(n)) ``` where `α` is the inverse Ackermann function. It grows so slowly that it is below 5 for any practical input size. The useful interpretation is *amortized almost constant time*, not literally constant time: one particular `find` may still walk a path, and the bound applies across the operation sequence. | implementation | worst tree height | amortized operation cost | | --- | ---: | ---: | | arbitrary linking | `O(n)` | `O(n)` | | union by size/rank | `O(log n)` | `O(log n)` | | size/rank + path compression | — | `O(α(n))` | Space is `O(n)`. ## what it does not maintain Union–find remembers connectivity, not the edges that established it. It cannot list a path between two elements unless another graph representation keeps the edges. It also does not efficiently support splitting a set or deleting an arbitrary union: one removed edge may or may not disconnect the component, and the parent forest contains too little information to decide. For a changing graph, common choices are: - process additions online and rebuild after deletions; - answer an offline sequence in reverse, turning deletions into unions; - use rollback union–find with a segment tree over time; - use a fully dynamic connectivity structure when the added complexity is justified. Path compression conflicts with simple rollback because one `find` mutates many parents. Rollback implementations usually omit compression, use union by size, and record each changed word on a stack. ## applications - connected components in an incrementally built undirected graph; - Kruskal's minimum-spanning-tree algorithm, rejecting edges whose endpoints already share a representative; - percolation and image-component labeling; - equivalence classes in compilers, type inference, and symbolic processing; - offline connectivity and account/entity merging. The fit is strongest when relationships only accumulate during the lifetime of the structure. ## representation and correctness The fundamental invariant is that every parent chain terminates at exactly one root. Useful debug checks include: - a root's stored size equals the number of elements that reach it; - the sum of root sizes equals the universe size; - non-root parents are valid indices; - `find(find(x)) == find(x)`; - a successful union decreases the number of roots by exactly one. Concurrency is not obtained by merely making parent words atomic. Two unions can race while choosing roots, lose a size update, or form a cycle. Concurrent variants need a defined linking order plus compare-and-swap loops, or a lock around mutations. Coarse locking is often the right first implementation because ordinary union–find operations are already very cheap. ## sources - Bernard A. Galler and Michael J. Fisher, “An Improved Equivalence Algorithm,” *Communications of the ACM* 7(5), 1964, [doi:10.1145/364099.364331](https://doi.org/10.1145/364099.364331). - Robert Endre Tarjan, “Efficiency of a Good But Not Linear Set Union Algorithm,” *Journal of the ACM* 22(2), 1975, [doi:10.1145/321879.321884](https://doi.org/10.1145/321879.321884). - Robert E. Tarjan and Jan van Leeuwen, “Worst-Case Analysis of Set Union Algorithms,” *Journal of the ACM* 31(2), 1984, [doi:10.1145/62.2160](https://doi.org/10.1145/62.2160). ### in these projects - [Coral's lattice](https://tangled.org/zzstoatzz.io/coral/blob/main/backend/src/lattice.zig) uses a negative-size parent array, weighted union, and full path compression to track connected occupied sites and detect percolation. Because expiring a site is a deletion, it periodically rebuilds the structure from live sites.