Union-Find (Disjoint Sets)

Disjoint sets with union by rank and path compression.

The idea

A disjoint-set structure, also called union-find, maintains a partition of $n$ elements into groups under two operations: $\text{Union}$ merges the two groups containing a given pair of elements, and $\text{Find}$ returns a group's representative, one canonical member standing for the whole group. Two elements lie in the same group exactly when $\text{Find}$ returns the same representative for both, so one equality test decides membership. This is the query behind connected-component tests and the graph algorithms that must avoid closing a cycle.

The representation is a forest of parent pointers. Each group is a tree, and its root, the element that points to itself, is the representative. $\text{Find}$ follows parent pointers upward to the root, and $\text{Union}$ locates both roots and hangs one under the other. An operation therefore costs the height of a tree, and careless linking can stretch a tree into a path of $n$ elements, making every $\text{Find}$ linear.

Two refinements, built into the operations below, prevent this.

Algorithm.

Algorithm: Find Input: an element x Output: the representative of x's group 1. follow parent pointers from x up to the root r // the root is the element that is its own parent 2. path compression: re-point every node visited along the way directly at r 3. return r

Algorithm.

Algorithm: Union Input: two elements x and y Output: none — their two groups become one 1. r = Find(x), r' = Find(y) // by the steps above if r = r', return // the two elements already share a group 2. union by rank: hang the lower-rank root beneath the higher // rank = an upper bound on the tree's height if the ranks are equal, hang either beneath the other and raise the surviving root's rank by 1

Union by rank keeps every tree shallow: height grows only when two equal-rank trees merge, which forces a rank-$r$ tree to hold at least $2^{r}$ elements, so ranks stay logarithmic. Path compression pays off on repeated queries: a $\text{Find}$ that walks the path $x \to a \to b \to r$ leaves $x$ and $a$ pointing straight at the root $r$, so asking again takes one hop.

With both, any $m$ operations on $n$ elements cost $O(m\,\alpha(n))$ in total, where the inverse Ackermann function $\alpha(n)$ is below $5$ for every practical $n$ — effectively constant per operation.

Ways to work on it

• Walkthrough. The forest representation, union by rank, and path compression.
• Practice. Count the disjoint sets remaining after a run of unions.
• Hardest. Bound the amortized cost of a long sequence of operations.

Not sure where to start? Take the ten-question placement test.