---
title: Disjoint Sets (Union-Find)
module: Data Structures
moduleNumber: 4
lessonNumber: 6
order: 406
summary: |
  The disjoint-set data structure tracks a partition of elements into groups,
  answering "are these two in the same group?" and merging groups on demand. A
  forest of parent pointers, sped up by union by rank and path compression,
  drives every operation to near-constant $O(\alpha(n))$ amortized time — the
  structure behind connectivity queries and Kruskal's minimum spanning tree.
topics: [Disjoint Sets, Amortized Analysis]
sources:
  - book: CLRS
    ref: "Ch. 21 — Data Structures for Disjoint Sets"
  - book: Skiena
    ref: "§6.1 — Union-Find"
  - book: Erickson
    ref: "Ch. — Disjoint Sets"
practice:
  - title: 'Number of Provinces'
    slug: number-of-provinces
    difficulty: Medium
  - title: 'Redundant Connection'
    slug: redundant-connection
    difficulty: Medium
  - title: 'Accounts Merge'
    slug: accounts-merge
    difficulty: Medium
  - title: 'Most Stones Removed with Same Row or Column'
    slug: most-stones-removed-with-same-row-or-column
    difficulty: Medium
  - title: 'Number of Islands'
    slug: number-of-islands
    difficulty: Medium
---

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](/algorithms/graphs/representations-and-traversal) create a cycle? The **disjoint-set** (or **union-find**) data structure
answers exactly these questions, and does so in _near-constant_ [amortized](/algorithms/foundations/asymptotic-analysis) time
per operation[^clrs-djs], slow-growing enough that for any realistic input 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)$ $\textsc{Decrease-Key}$) shaves it toward $O(m + n \log n)$.
[Kruskal's MST](/algorithms/graphs/minimum-spanning-trees) illustrates the same point with 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 improve it from $\Theta(n)$ per query down to inverse Ackermann.

## The disjoint-set ADT

We maintain a collection $\set{S_1, S_2, \dots, S_k}$ 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:

- $\textsc{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.
- $\textsc{Find-Set}(x)$ returns the representative of the set containing $x$. Two
  elements are in the same set _iff_ they return the same representative.
- $\textsc{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
$\textbf{Find-Set}(x) = \textbf{Find-Set}(y)$. After $n$ $\textsc{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**.[^erickson-djs] 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.

$$
% caption: Two disjoint-set trees of parent pointers, each root looping to itself
\begin{tikzpicture}[
  every node/.style={circle, draw, minimum size=8mm, inner sep=0},
  >=stealth]
  % tree 1, root c
  \node (c) at (0,0) {$c$};
  \node (a) at (-0.9,-1.2) {$a$};
  \node (h) at (0.9,-1.2) {$h$};
  \node (b) at (0.9,-2.4) {$b$};
  \draw[->] (a) -- (c);
  \draw[->] (h) -- (c);
  \draw[->] (b) -- (h);
  % tree 2, root f
  \begin{scope}[xshift=46mm]
    \node (f) at (0,0) {$f$};
    \node (d) at (-0.9,-1.2) {$d$};
    \node (e) at (0.9,-1.2) {$e$};
    \draw[->] (d) -- (f);
    \draw[->] (e) -- (f);
  \end{scope}
  \draw[->] (c) edge[loop above] ();
  \draw[->] (f) edge[loop above] ();
\end{tikzpicture}
$$

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

```algorithm
caption: Naive disjoint-set forest operations
Make-Set(x):
  $parent(x) \gets x$
Find-Set(x):
  while $x \ne parent(x)$ do
    $x \gets parent(x)$ // walk to the root
  return $x$
Union(x, y):
  $parent(\textbf{Find-Set}(x)) \gets \textbf{Find-Set}(y)$
```

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 $\textsc{Find-Set}$ cost $\Theta(n)$.
Two heuristics, used together, flatten the forest and make the structure
fast.

::impl{algo="naive_disjoint_forest"}

## 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 efficient. Keep an array $comp[\,]$ that stores, for
each element, a _label_ naming its current set. Then $\textsc{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 is in $\textsc{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:

> **Remark (Union by size).** Always relabel the _smaller_ set. When uniting the sets of $u$ and $v$,
> rewrite the labels of whichever set has _fewer_ members, and keep the larger
> set's label.

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?

> **Claim (relabel cost).** Over any sequence of unions on $n$ elements,
> relabel-the-smaller does $O(n \log n)$ total label rewrites — even though a
> single union may still touch $\Theta(n)$ elements.

> **Proof.** 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, the total is $O(n \log n)$. $\qed$

This small example already shows the idea: a structurally trivial rule (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})$.

::impl{algo="union_by_size_labels"}

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

$$
% caption: The same four unions, two ways. Careless linking builds a height-$3$ chain;
%          union by rank keeps height $1$ — every $\textsc{Find-Set}$ is then one hop
\begin{tikzpicture}[
  vtx/.style={circle, draw, minimum size=7mm, inner sep=0, font=\small},
  >=stealth]
  \definecolor{acc}{HTML}{2348F2}
  % --- careless: a path a<-b<-c<-d ---
  \node[vtx] (a) at (0,0) {$a$};
  \node[vtx] (b) at (0,-1.0) {$b$};
  \node[vtx] (c) at (0,-2.0) {$c$};
  \node[vtx] (d) at (0,-3.0) {$d$};
  \draw[->] (d) -- (c);
  \draw[->] (c) -- (b);
  \draw[->] (b) -- (a);
  \draw[->] (a) edge[loop left] ();
  \node[draw=none, font=\footnotesize] at (0,0.8) {careless: height $3$};
  \node[draw=none, font=\footnotesize, text=acc] at (1.75,-1.5) {\textsc{Find}$(d)$: 3 hops};
  % --- union by rank: star ---
  \begin{scope}[xshift=52mm, yshift=-15mm]
    \node[vtx] (ra) {$a$};
    \node[vtx] (rb) [below left=10mm and 11mm of ra] {$b$};
    \node[vtx] (rc) [below=10mm of ra] {$c$};
    \node[vtx] (rd) [below right=10mm and 11mm of ra] {$d$};
    \draw[->] (rb) -- (ra);
    \draw[->] (rc) -- (ra);
    \draw[->] (rd) -- (ra);
    \draw[->] (ra) edge[loop above] ();
    \node[draw=none, font=\footnotesize] at (0,1.35) {union by rank: height $1$};
    \node[draw=none, font=\footnotesize, text=acc] at (0,-2.4) {\textsc{Find}$(d)$: 1 hop};
  \end{scope}
\end{tikzpicture}
$$

## 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 a logarithmic height bound:

> **Lemma (rank bound).** Under union by rank, every tree of rank $r$ contains at
> least $2^r$ nodes; hence rank, and so height, is at most $\log_2 n$, and every
> operation is $O(\log n)$.

> **Proof.** Induct on $r$. A rank-$0$ tree is a single node, so it holds
> $2^0 = 1$. A root reaches rank $r$ only by uniting two trees that were both rank
> $r-1$, each holding $\ge 2^{r-1}$ nodes by the induction hypothesis, so the
> merged tree holds $\ge 2 \cdot 2^{r-1} = 2^r$ nodes. A tree of $n$ nodes
> therefore has rank $\le \log_2 n$. $\qed$

$$
% caption: The smallest trees union by rank can produce at each rank. A root's rank
%          rises only when two equal-rank trees merge, and that merge at least doubles
%          the node count, so a rank-$r$ tree holds $\ge 2^r$ nodes: $1, 2, 4, 8, \dots$
%          — capping rank (and height) at $\log_2 n$.
\begin{tikzpicture}[
  vtx/.style={circle, draw, minimum size=4.5mm, inner sep=0},
  clab/.style={draw=none, font=\scriptsize},
  >=stealth, x=1cm, y=1cm]
  \definecolor{acc}{HTML}{2348F2}
  % rank 0: single node
  \node[vtx] (a0) at (0,0) {};
  \node[clab] at (0,0.75) {rank 0};
  \node[clab, text=acc] at (0,-3.3) {$1$};
  % rank 1: two nodes
  \begin{scope}[xshift=16mm]
    \node[vtx] (b0) at (0,0) {};
    \node[vtx] (b1) at (0,-0.9) {};
    \draw[->] (b1) -- (b0);
    \node[clab] at (0,0.75) {rank 1};
    \node[clab, text=acc] at (0,-3.3) {$2$};
  \end{scope}
  % rank 2: four nodes
  \begin{scope}[xshift=38mm]
    \node[vtx] (c0) at (0,0) {};
    \node[vtx] (c1) at (-0.55,-0.9) {};
    \node[vtx] (c2) at (0.55,-0.9) {};
    \node[vtx] (c3) at (-0.55,-1.8) {};
    \draw[->] (c1) -- (c0);
    \draw[->] (c2) -- (c0);
    \draw[->] (c3) -- (c1);
    \node[clab] at (0,0.75) {rank 2};
    \node[clab, text=acc] at (0,-3.3) {$4$};
  \end{scope}
  % rank 3: eight nodes (root gains children of ranks 2, 1, 0)
  \begin{scope}[xshift=72mm]
    \node[vtx] (d0) at (0,0) {};
    \node[vtx] (d1) at (-1.1,-0.9) {};
    \node[vtx] (d2) at (0,-0.9) {};
    \node[vtx] (d3) at (1.1,-0.9) {};
    \node[vtx] (d4) at (-1.65,-1.8) {};
    \node[vtx] (d5) at (-0.55,-1.8) {};
    \node[vtx] (d6) at (0,-1.8) {};
    \node[vtx] (d7) at (-1.65,-2.7) {};
    \draw[->] (d1) -- (d0);
    \draw[->] (d2) -- (d0);
    \draw[->] (d3) -- (d0);
    \draw[->] (d4) -- (d1);
    \draw[->] (d5) -- (d1);
    \draw[->] (d6) -- (d2);
    \draw[->] (d7) -- (d4);
    \node[clab] at (0,0.75) {rank 3};
    \node[clab, text=acc] at (0,-3.3) {$8$};
  \end{scope}
  \node[clab, text=acc, anchor=east] at (-0.8,-3.3) {min size:};
\end{tikzpicture}
$$
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 $\textsc{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.

$$
% caption: Union by rank hangs the lower-rank root beneath the higher-rank root
\begin{tikzpicture}[
  >=Stealth,
  vtx/.style={circle, draw, minimum size=8mm, inner sep=0},
  node distance=10mm and 7mm]
  % --- before: two trees ---
  \node[vtx] (c) {$c$};
  \node[vtx] (a) [below left=of c] {$a$};
  \node[vtx] (h) [below right=of c] {$h$};
  \node[vtx] (b) [below=of h] {$b$};
  \draw[->] (a) -- (c);
  \draw[->] (h) -- (c);
  \draw[->] (b) -- (h);
  \draw[->] (c) edge[loop above] ();
  \node[font=\footnotesize] at (c |- b) {rank $2$};

  \node[vtx] (f) [right=26mm of c] {$f$};
  \node[vtx] (d) [below left=of f] {$d$};
  \node[vtx] (e) [below right=of f] {$e$};
  \draw[->] (d) -- (f);
  \draw[->] (e) -- (f);
  \draw[->] (f) edge[loop above] ();
  \node[font=\footnotesize] at (f |- b) {rank $1$};

  % union arrow (in the clear band between the two panels, above the trees)
  \draw[->, thick] ($(f)+(1.2,0.6)$)
    -- node[above, font=\footnotesize, draw=none, fill=white, inner sep=1.5pt] {$\textsc{Union}(b,e)$} ($(f)+(3.0,0.6)$);

  % --- after: f hung under c ---
  \begin{scope}[xshift=92mm]
    \node[vtx] (c2) at (0,0) {$c$};
    \node[vtx] (a2) at (-2.0,-1.3) {$a$};
    \node[vtx] (f2) at (0,-1.3) {$f$};
    \node[vtx] (h2) at (2.0,-1.3) {$h$};
    \node[vtx] (d2) at (-0.8,-2.7) {$d$};
    \node[vtx] (e2) at (0.8,-2.7) {$e$};
    \node[vtx] (b2) at (2.0,-2.7) {$b$};
    \draw[->] (a2) -- (c2);
    \draw[->] (h2) -- (c2);
    \draw[->] (f2) -- (c2);
    \draw[->] (d2) -- (f2);
    \draw[->] (e2) -- (f2);
    \draw[->] (b2) -- (h2);
    \draw[->] (c2) edge[loop above] ();
    \node[font=\footnotesize] at (2.7,0) {rank $2$};
  \end{scope}
\end{tikzpicture}
$$

## Heuristic 2: path compression

**Path compression** attacks the cost from the other side. Each time
$\textsc{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 $\textsc{Find-Set}$ on those nodes is then a single hop.

$$
% caption: Path compression points every node on a Find-Set path straight at the root
\begin{tikzpicture}[
  every node/.style={circle, draw, minimum size=7mm, inner sep=0},
  >=stealth, level distance=10mm]
  % before: a chain
  \node (r) {$r$}
    child {node (w) {$w$}
      child {node (v) {$v$}
        child {node (u) {$u$}}
      }
    };
  \draw[->] (r) edge[loop above] ();
  \draw[->, thick] (2.7,-1.5) -- node[draw=none, above, font=\footnotesize] {Find-Set$(u)$} (4.0,-1.5);
  % after: flattened
  \begin{scope}[xshift=58mm]
    \node (r2) {$r$};
    \node (u2) [below left=10mm and 11mm of r2] {$u$};
    \node (v2) [below=10mm of r2] {$v$};
    \node (w2) [below right=10mm and 11mm of r2] {$w$};
    \draw[->] (u2) -- (r2);
    \draw[->] (v2) -- (r2);
    \draw[->] (w2) -- (r2);
    \draw[->] (r2) edge[loop above] ();
  \end{scope}
\end{tikzpicture}
$$

Before, $u$ sits at the bottom of a chain $u \to v \to w \to r$; after
$\textsc{Find-Set}(u)$, the nodes $u$, $v$, $w$ all point straight at $r$. The
$\textsc{Find-Set}$ that pays for the walk leaves the tree much flatter for
every later operation.

```algorithm
caption: $\textsc{Find-Set}(x)$ — with path compression (recursive)
if $x \ne parent(x)$ then
  $parent(x) \gets$ call $\textsc{Find-Set}(parent(x))$ // point x at the root
return $parent(x)$
```

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 drive the disjoint-set
structure's cost to near-constant.

> **Theorem (Tarjan).** A sequence of $m$ $\textsc{Make-Set}$, **Union**, and
> $\textsc{Find-Set}$ operations on $n$ elements, using union by rank and path
> compression, runs in $O\parens{m\,\alpha(n)}$ time, where $\alpha(n)$ is the
> inverse Ackermann function.

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)$.[^clrs-ackermann]

The two heuristics achieve 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.

::impl{algo="union_find"}

### A worked trace: both heuristics together

For a trace of the two heuristics together, start with seven
singletons $a, b, c, d, e, f, g$, each its own tree of rank $0$, and process this
sequence of operations:

$$
\textsc{Union}(a,b),\;\;
\textsc{Union}(c,d),\;\;
\textsc{Union}(a,c),\;\;
\textsc{Union}(e,f),\;\;
\textsc{Union}(a,e),\;\;
\textsc{Find-Set}(d).
$$

Union by rank governs each merge, breaking ties by keeping the first-named root.

1. **$\textsc{Union}(a,b)$.** Both rank $0$; equal ranks, so hang $b$ under $a$
   and bump $a$ to rank $1$. Tree: $a \leftarrow b$.
2. **$\textsc{Union}(c,d)$.** Both rank $0$; hang $d$ under $c$, $c$ becomes
   rank $1$. Tree: $c \leftarrow d$.
3. **$\textsc{Union}(a,c)$.** Both roots have rank $1$; equal ranks, so hang $c$
   under $a$ and bump $a$ to rank $2$. Now $a$ has children $b$ and $c$, and $c$
   still has child $d$: $d$ sits at depth $2$.
4. **$\textsc{Union}(e,f)$.** Both rank $0$; hang $f$ under $e$, $e$ to rank $1$.
5. **$\textsc{Union}(a,e)$.** $a$ has rank $2$, $e$ has rank $1$; ranks differ,
   so hang the smaller-rank root $e$ under $a$ and **no rank changes** ($a$ stays
   rank $2$). The tree rooted at $a$ now holds all seven elements, with $d$ and
   $f$ at depth $2$.
6. **$\textsc{Find-Set}(d)$.** Walk $d \to c \to a$ to reach root $a$, then
   **compress**: point $d$ (and $c$, already a child of $a$) straight at $a$. The
   next $\textsc{Find-Set}(d)$ is a single hop.

$$
% caption: The forest after the five unions (left), and after $\textsc{Find-Set}(d)$
%          compresses $d$'s path (right). Union by rank kept the tree at height $2$;
%          path compression then pulls $d$ up to be a direct child of the root $a$, so
%          its next lookup costs one hop. Ranks are shown beside each root.
\begin{tikzpicture}[
  vtx/.style={circle, draw, minimum size=7mm, inner sep=0, font=\small},
  lbl/.style={draw=none, font=\scriptsize},
  >=stealth]
  \definecolor{acc}{HTML}{2348F2}
  \definecolor{green}{HTML}{1F9E55}
  % --- before compression ---
  \node[vtx] (a) at (0,0) {$a$};
  \node[vtx] (b) at (-1.6,-1.2) {$b$};
  \node[vtx] (c) at (0,-1.2) {$c$};
  \node[vtx] (e) at (1.6,-1.2) {$e$};
  \node[vtx] (d) at (-0.5,-2.4) {$d$};
  \node[vtx] (f) at (1.6,-2.4) {$f$};
  \draw[->] (b) -- (a);
  \draw[->] (c) -- (a);
  \draw[->] (e) -- (a);
  \draw[->] (d) -- (c);
  \draw[->] (f) -- (e);
  \draw[->] (a) edge[loop above] ();
  \node[lbl, acc, anchor=west] at (a.east) {rank $2$};
  \node[lbl] at (0,-3.2) {after 5 unions};
  % arrow
  \draw[->, thick] (2.6,-1.2) -- node[lbl, above] {$\textsc{Find}(d)$} (4.0,-1.2);
  % --- after compression ---
  \begin{scope}[xshift=68mm]
    \node[vtx] (a2) at (0,0) {$a$};
    \node[vtx] (b2) at (-1.8,-1.2) {$b$};
    \node[vtx] (c2) at (-0.6,-1.2) {$c$};
    \node[vtx, draw=green, thick] (d2) at (0.6,-1.2) {$d$};
    \node[vtx] (e2) at (1.8,-1.2) {$e$};
    \node[vtx] (f2) at (1.8,-2.4) {$f$};
    \draw[->] (b2) -- (a2);
    \draw[->] (c2) -- (a2);
    \draw[->, green, thick] (d2) -- (a2);
    \draw[->] (e2) -- (a2);
    \draw[->] (f2) -- (e2);
    \draw[->] (a2) edge[loop above] ();
    \node[lbl, acc, anchor=west] at (a2.east) {rank $2$};
    \node[lbl] at (0,-3.2) {$d$ now one hop from root};
  \end{scope}
\end{tikzpicture}
$$

Two details from this run are worth stating precisely. First, only step 1, 2, 3, 4
ever raised a rank, and each raise required merging two trees of _equal_ rank,
exactly the doubling that caps rank at $\log_2 n$. Step 5 merged unequal ranks
and left every rank untouched, which is the common case in practice. Second,
notice that after compression $d$'s rank-based ancestor $c$ is still recorded as
rank $1$ even though $c$ is now a leaf, this is why ranks are only an _upper
bound_ on height, and why the heuristic keeps the name "rank" rather than
"height."

## Application: connectivity and minimum spanning trees

Two applications make the structure indispensable.

**Connectivity.** Given a graph, call $\textsc{Make-Set}$ on every vertex, then
$\textsc{Union}(u, v)$ for every edge $\set{u, v}$. Afterward,
$\textbf{Find-Set}(u) = \textbf{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 $\textsc{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 $\set{u, v}$ 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.[^skiena-djs]

$$
% caption: Kruskal as union-find. Scanning edges by weight, each is accepted iff its
%          endpoints have different roots; the rejected edge $\{b,c\}$ closes a cycle
%          since $b,c$ already share a set
\begin{tikzpicture}[
  vtx/.style={circle, draw, minimum size=7mm, inner sep=0, font=\small},
  >=stealth, node distance=14mm]
  \definecolor{acc}{HTML}{2348F2}
  \node[vtx] (a) at (0,0) {$a$};
  \node[vtx] (b) at (1.6,0.7) {$b$};
  \node[vtx] (c) at (1.6,-0.7) {$c$};
  \node[vtx] (d) at (3.2,0) {$d$};
  \draw[acc, very thick] (a) -- node[draw=none,font=\footnotesize,above left=-1pt]{$1$} (b);
  \draw[acc, very thick] (a) -- node[draw=none,font=\footnotesize,below left=-1pt]{$2$} (c);
  \draw[acc, very thick] (b) -- node[draw=none,font=\footnotesize,above right=-1pt]{$3$} (d);
  \draw[red, dashed, thick] (b) -- node[draw=none,font=\footnotesize,right]{$4$} (c);
  \node[draw=none, font=\footnotesize, text=red] at (1.6,-1.6) {$\{b,c\}$ rejected: same set};
  \begin{scope}[xshift=52mm, yshift=2mm]
    \node[draw=none, font=\footnotesize, align=left, anchor=north west] at (0,0)
      {$\{a,b\}\,1$: \textsc{Union} $\to \{a,b\}$\\[1pt]
       $\{a,c\}\,2$: \textsc{Union} $\to \{a,b,c\}$\\[1pt]
       $\{b,d\}\,3$: \textsc{Union} $\to \{a,b,c,d\}$\\[1pt]
       $\{b,c\}\,4$: \textsc{Find} $b=$ \textsc{Find} $c$ -- skip};
  \end{scope}
\end{tikzpicture}
$$

```algorithm
caption: $\textsc{MST-Kruskal}(G, w)$ — minimum spanning tree via union-find
$A \gets \emptyset$
foreach vertex $v$ in $V[G]$ do
  call $\textsc{Make-Set}(v)$
sort the edges of $G$ into nondecreasing order by weight $w$
foreach edge $\set{u, v}$ in that order do
  if call $\textsc{Find-Set}(u) \ne$ call Find-Set$(v)$ then
    $A \gets A \cup \set{\,\set{u, v}\,}$ // joins two components
    call $\textsc{Union}(u, v)$
return $A$
```

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)$
$\textsc{Find-Set}$ tests and $O(n)$ $\textsc{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:

$$
T(m, n) = \underbrace{O(m \log m)}_{\text{sort}} \;=\; O(m \log n).
$$

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 what makes Kruskal both simple and fast.

::impl{algo="connected_components,kruskal_mst"}

## Lower bounds, and where union-find runs

Two threads extend the textbook treatment, one theoretical and one practical.

**The bound is tight, and $\alpha(n)$ is unavoidable.** It is natural to suspect
the inverse-Ackermann factor is an artifact of a loose analysis, that a cleverer
argument would prove $O(m)$. It cannot. Fredman and Saks (1989) proved a matching
_lower bound_: in the cell-probe model, any data structure for the disjoint-set
problem must spend $\Omega(m\,\alpha(n))$ time on some sequence of $m$
operations. So Tarjan's analysis is not merely the best known, it is the best
possible, and $\alpha(n)$ is an intrinsic feature of the problem, not of the
algorithm. The function itself is the inverse of the fast-growing
**Ackermann function** $A(k, j)$, whose rows climb from addition ($A(1,\cdot)$)
to multiplication, exponentiation, towers of exponents, and beyond; $\alpha(n)$
asks how many rows up you must go before the values exceed $n$, and the answer
is at most $4$ for any $n$ that could be written down.

**Beyond the merge-only model.** Plain union-find handles only _incremental_
connectivity, edges arrive and components merge, never split. Two extensions
answer harder queries. A **union-find with rollback** (used inside offline
dynamic-connectivity algorithms) forgoes path compression, so that unions can be
undone in a stack discipline; it keeps $O(\log n)$ per operation but supports a
_decremental_ or fully offline stream of edge insertions and deletions. And the
**Euler-tour / link-cut** structures solve _fully dynamic_ connectivity, edges
inserted and deleted online, in $O(\log^2 n)$ amortized time, well outside what
parent pointers can do. In practice, the merge-only structure is enough for the
dominant applications: **Kruskal's MST**, connected-component labeling in image
segmentation (the Felzenszwalb–Huttenlocher segmenter is union-find on a pixel
graph, edges scanned by weight exactly as in Kruskal), percolation simulations,
and the type-inference "union" of equivalence classes in compilers.[^btb-djs]

## Takeaways

- The **disjoint-set** ADT — $\textsc{Make-Set}$, $\textsc{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; $\textsc{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 $\textsc{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 doubles as 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 comes from the disjoint-set
  structure underneath.

[^clrs-djs]: **CLRS**, Ch. 21 — Data Structures for Disjoint Sets (§21.1): the Make-Set/Find-Set/Union ADT and its near-constant amortized cost.
[^erickson-djs]: **Erickson**, Ch. — Disjoint Sets: the parent-pointer forest representation of a partition.
[^clrs-ackermann]: **CLRS**, Ch. 21 — Data Structures for Disjoint Sets (§21.4): Tarjan's $O(m\,\alpha(n))$ inverse-Ackermann amortized bound.
[^skiena-djs]: **Skiena**, §6.1 — Union-Find: the cycle test in Kruskal's MST coincides with the same-set query.
[^btb-djs]: Fredman & Saks, "The cell probe complexity of dynamic data structures" (1989), for the $\Omega(m\,\alpha(n))$ lower bound; Felzenszwalb & Huttenlocher, "Efficient graph-based image segmentation" (2004), for union-find segmentation; Holm, de Lichtenberg & Thorup, "Poly-logarithmic deterministic fully-dynamic algorithms for connectivity" (2001), for fully dynamic connectivity.