Disjoint Sets (Union-Find)

Some problems keep a collection of items partitioned into disjoint groups that only ever merge, never split, and repeatedly ask whether two items currently share a group. Are these two cities on the same electrical grid? Do these two pixels belong to the same connected region? Does adding this edge to a graph create a cycle? The disjoint-set (or union-find) data structure answers exactly these questions, and does so in near-constant amortized time per operation¹, slow-growing enough that for every input you will ever see, it is effectively $O(1)$.

There is a recurring lesson in the design of efficient algorithms: the right data structure is what makes an algorithm fast. Dijkstra's and Prim's shortest- path and MST algorithms are correct with any priority queue, but their speed hinges on the queue: a binary heap gives $O(m\log n)$, while a Fibonacci heap (with amortized $O(1)$ $\text{Decrease-Key}$) shaves it toward $O(m+n\log n)$. Kruskal's MST tells the same story through a different structure. The algorithm is one line of logic, and every bit of its efficiency comes from the disjoint-set structure beneath it. We will build that structure from the ground up and watch it collapse from $\Theta (n)$ per query down to inverse Ackermann.

The disjoint-set ADT

We maintain a collection $\left\{S_1,S_2,\dots ,S_k\right\}$ of disjoint sets that together partition a universe of elements. Each set is named by a representative, some fixed member of the set chosen by the structure. The ADT has three operations:

• $\text{Make-Set}(x)$ creates a new set whose only member is $x$ (so $x$ is its own representative). $x$ must not already be in any set.
• $\text{Find-Set}(x)$ returns the representative of the set containing $x$. Two elements are in the same set iff they return the same representative.
• $\text{Union}(x,y)$ merges the sets containing $x$ and $y$ into one, picking a representative for the combined set. The two old sets are destroyed.

The query are $x$ and $y$ together? is just the test $\text{Find-Set}(x)=\text{Find-Set}(y)$. After $n$ $\text{Make-Set}$ operations there can be at most $n-1$ Union operations, since each union reduces the number of sets by one.

The forest representation

The fast implementation represents each set as a rooted tree, and the whole collection as a forest.² Every element points only to its parent; the root of each tree is the set's representative and points to itself. There are no child pointers and no key ordering. This is not a search tree, just a tangle of upward pointers whose only job is to lead to a root.

Two sets: $\left\{a,b,c,h\right\}$ with representative $c$, and $\left\{d,e,f\right\}$ with representative $f$. Each node's single arrow points at its parent; the roots loop to themselves. $\text{Find-Set}$ follows parent pointers up to the root; Union makes one tree's root a child of the other's.

So far this is correct but not fast: a careless sequence of unions can build a tall, skinny tree, a path of $n$ nodes, making $\text{Find-Set}$ cost $\Theta (n)$. Two heuristics, used together, flatten the forest and make the structure extraordinarily fast.

A warm-up: labels, and always relabel the smaller side

Before the forest, consider the most naive possible implementation, along with the one idea that already makes it respectable. Keep an array $comp[]$ that stores, for each element, a label naming its current set. Then $\text{Find-Set}(x)$ is just $comp[x]$, a single array lookup, and the same-set test $comp[u]=comp[v]$ is instant. The whole cost lives in $\text{Union}$: merging two sets means walking through one of them and rewriting every member's label to match the other.

The question is which set to rewrite. If we are careless and always relabel, say, the set containing $u$, an adversary can force $\Theta (n)$ work on every union. The fix is a single disciplined rule:

To do this efficiently, alongside $comp[]$ keep a list $members[\ell ]$ of the elements currently carrying label $\ell$, plus each set's size; the union then splices the smaller list into the larger and relabels only the short side.

Why does this help so much? Charge the cost to the elements that get relabeled. An element's label changes only when it sits in the smaller of two merging sets, and after that merge, the set it belongs to is at least twice as big as before. A set can double in size at most ${\log }_{2}n$ times before it swallows the whole universe, so each element is relabeled at most ${\log }_{2}n$ times over the entire run. Summed over all $n$ elements, all of the union work together costs $O(n\log n)$, even though a single union might still touch $\Theta (n)$ elements.

This is the whole game in miniature: a structurally trivial idea (relabel the smaller side) plus an amortized doubling argument turns a quadratic-looking cost into $O(n\log n)$. The forest representation below keeps exactly this intuition, the smaller thing yields to the larger, but replaces the explicit relabeling with a single pointer move, so a union becomes $O(1)$ instead of $O(\text{size})$.

Everything now hinges on which root we hang beneath the other. Get it wrong and the forest degenerates into exactly the chain we feared; get it right and the trees stay flat. The figure contrasts the two outcomes of the same four merges.

Heuristic 1: union by rank

The trouble is unions that make a tall tree a child of a short one, deepening it. Union by rank prevents this. Each root carries a rank, an upper bound on the height of its tree. When uniting two trees, we attach the root of smaller rank beneath the root of larger rank, so the taller tree's height never grows. Only when the two ranks are equal does the height increase, and then by exactly one (and we bump the surviving root's rank).

This single rule already guarantees that every tree of rank $r$ contains at least $2^r$ nodes, so rank, and hence height, is at most ${\log }_{2}n$. With union by rank alone, every operation is $O(\log n)$.

Notice this is the same doubling argument from the warm-up, read from the other direction: there, a set doubled each time an element was relabeled; here, a root's rank rises only when two equal-rank trees merge, which doubles the node count. Either way, ${\log }_{2}n$ is the ceiling, because nothing can double more than that many times.

The figure shows a $\text{Union}$ under this rule. The left tree has rank $2$, the right rank $1$; since their ranks differ, the smaller-rank root $f$ is hung beneath the larger-rank root $c$ and no rank changes. The result still has rank $2$, exactly as the warm-up's smaller side yields to the larger demands, but now it costs a single pointer move rather than relabeling every member.

Heuristic 2: path compression

Path compression attacks the cost from the other side. Each time $\text{Find-Set}(x)$ walks up to the root, it makes a second pass and points every node it visited directly at the root. The path is paid for once; every future $\text{Find-Set}$ on those nodes is then a single hop.

Before, $u$ sits at the bottom of a chain $u\to v\to w\to r$; after $\text{Find-Set}(u)$, the nodes $u$, $v$, $w$ all point straight at $r$. The $\text{Find-Set}$ that pays for the walk leaves the tree dramatically flatter for everyone behind it.

The recursion bottoms out at the root, and as it unwinds it reassigns every node's parent to that root. With path compression in use, the rank of a root is only an upper bound on its height (compression can make the tree shorter than its rank suggests), which is why the heuristic is called union by rank rather than by height.

The near-constant amortized bound

Used together, union by rank and path compression make the disjoint-set structure almost unbelievably fast.

The function $\alpha (n)$ grows so slowly it is practically constant: $\alpha (n)\le 4$ for every $n$ up to roughly $2^{2^{2^{16}}}$, a number far larger than the count of atoms in the universe. So for any conceivable input, each operation costs amortized $O(1)$.³

The two heuristics earn this by attacking complementary failure modes: union by rank keeps trees from getting tall in the first place (height $\le \log n$), while path compression ensures that any depth a tree does accumulate gets paid down and reused, so the expensive walks cannot recur. Neither alone gives $\alpha (n)$ (union by rank alone is $O(\log n)$ amortized, path compression alone is $O(\log n)$ amortized), but their combination collapses to inverse Ackermann. The full proof uses a subtle potential-function (amortized) argument, charging each node's cost against the steady growth of the ranks above it. The intuition to keep is that a node can be lifted closer to the root only so many times before it is the root's child, and ranks climb too slowly for that to happen often.

Application: connectivity and minimum spanning trees

Two applications make the structure indispensable.

Connectivity. Given a graph, call $\text{Make-Set}$ on every vertex, then $\text{Union}(u,v)$ for every edge $\left\{u,v\right\}$. Afterward, $\text{Find-Set}(u)=\text{Find-Set}(v)$ holds iff $u$ and $v$ lie in the same connected component. The structure also processes online edge insertions: each new edge is one Union, and connectivity queries between insertions are each one pair of $\text{Find-Set}$ calls, both amortized $O(\alpha (n))$.

Kruskal's minimum spanning tree. Kruskal's algorithm builds a minimum spanning tree by scanning edges in increasing weight order and adding each edge unless it would form a cycle. An edge $\left\{u,v\right\}$ forms a cycle exactly when $u$ and $v$ are already connected (i.e. already in the same set), which is the disjoint-set query verbatim.⁴

Now read off the running time. Sorting the edges costs $O(m\log m)$, and since a simple graph has $m\le n^2$ edges we have $\log m\le 2\log n$, so the sort is $O(m\log n)$, and this dominates. The disjoint-set work spans $O(m)$$\text{Find-Set}$ tests and $O(n)$ $\text{Union}$s; even with only the warm-up's relabel-the-smaller scheme this is $O(m+n\log n)$, already cheaper than the sort, and with the rank/compression forest it is $O(m\alpha (n))$, effectively linear. Either way:

The lesson here is worth stating plainly: Kruskal's logic is one acyclicity test per edge, but its efficiency is entirely a property of the structure answering that test. The cycle test is the same-set query, and a good disjoint-set structure is exactly what makes Kruskal both simple and fast.

Takeaways

• The disjoint-set ADT — $\text{Make-Set}$, $\text{Find-Set}$, Union — maintains a partition under merges and answers same group? by comparing representatives.
• A labels + relabel-the-smaller warm-up already costs only $O(n\log n)$ total: each element is relabeled $\le {\log }_{2}n$ times because its set doubles whenever it moves. This doubling argument is the seed of union by rank.
• The forest representation stores each set as a tree of parent pointers whose root is the representative; $\text{Find-Set}$ walks to the root, Union links two roots, turning the warm-up's $O(\text{size})$ relabel into one $O(1)$ pointer move.
• Union by rank keeps trees short (attach shorter under taller), and path compression flattens each $\text{Find-Set}$ path to point straight at the root.
• Together they give $O(\alpha (n))$ amortized time per operation — inverse Ackermann, so $\le 4$ for any realistic $n$, i.e. effectively constant.
• It powers connectivity queries and Kruskal's MST, where the same-set test is exactly the cycle test. Kruskal runs in $O(m\log n)$, with the sort, not the union-find, as the bottleneck.
• The unifying theme: clever data structures are what make algorithms fast. Kruskal's logic is one line; all of its speed lives in the disjoint-set structure underneath.