Disjoint sets & union-find

The connectivity structure

A disjoint-set (union-find) structure maintains a collection of non-overlapping sets, each named by a representative member, and answers "are these two elements in the same set?" extremely fast. Three operations:

• MAKE-SET(x) — create a singleton $\{x\}$. $O(1)$.
• UNION(x, y) — merge the sets containing $x$ and $y$ into one (destroying the originals).
• FIND-SET(x) — return the representative of $x$'s set.

The defining property: FIND-SET(u) == FIND-SET(v) iff $u$ and $v$ are in the same set. With $n$ MAKE-SET calls there can be at most $n-1$ UNIONs (each merge drops the set count by one). This is the workhorse behind connected components of a graph and, most importantly for this course, Kruskal's MST algorithm (Module 7): process edges cheapest-first, and add edge $(u,v)$ only when FIND-SET(u) != FIND-SET(v) (i.e. it joins two different components), then UNION them.

Disjoint-set forests and two heuristics

The efficient representation is a forest: each set is a rooted tree where every node points only to its parent, and the root (its own parent) is the representative. FIND-SET walks parent pointers up to the root; UNION links one root under another. Naively this can build a height-$(n-1)$ chain and make FIND-SET $O(n)$. Two heuristics fix it:

1. Union by rank — each node keeps a rank (an upper bound on its height). In a union, the root of smaller rank points to the root of larger rank; on a tie, pick either and bump its rank. This keeps trees shallow, analogous to the weighted-union heuristic for lists.
2. Path compression — during FIND-SET, make every node on the path point directly to the root. Since you walk to the root anyway, flattening is nearly free, and it makes future finds on those nodes $O(1)$. (Path compression never changes ranks — rank stays an upper bound on height, not the exact height.)

The running time: essentially linear

The bounds stack up:

• Naive forest: $O(n)$ per FIND-SET.
• Union by rank alone: $O(m\lg n)$ for $m$ operations.
• Union by rank + path compression: $O(m\alpha (n))$ — where $\alpha (n)$ is the inverse Ackermann function.

$\alpha (n)$ grows so absurdly slowly that $\alpha (n)\le 4$ for any $n$ up to the number of atoms in the observable universe ($\approx 10^{80}$). So $O(m\alpha (n))$ is "essentially linear" — effectively $O(1)$ amortized per operation — even though, technically, it is superlinear (Tarjan proved $\Omega (m\alpha (n))$ is also a lower bound, so you cannot do strictly better).

Worked example — six elements, four unions

Start with MAKE-SET on $\{0,1,2,3,4,5\}$ — six singletons, six components. Now UNION(0,1), UNION(2,3), UNION(1,3), UNION(4,5):

• UNION(0,1) merges $\{0\}$ and $\{1\}$ → $\{0,1\}$.
• UNION(2,3) → $\{2,3\}$.
• UNION(1,3) merges the $\{0,1\}$ and $\{2,3\}$ components (because $1$ is now in the same tree as $0$, and $3$ with $2$) → $\{0,1,2,3\}$.
• UNION(4,5) → $\{4,5\}$.

Now FIND-SET(0) == FIND-SET(3) is True (both in $\{0,1,2,3\}$), but FIND-SET(0) == FIND-SET(5) is False ($\{0,1,2,3\}$ vs $\{4,5\}$). Two components remain. Each FIND-SET after path compression points its path's nodes straight at the root, so repeated connectivity queries are effectively $O(1)$ — this is exactly the "are these two vertices already connected?" test Kruskal runs on every edge.