Disjoint Set Union (Union-Find) — path compression + union by rank → α(n): Foundations

Before you can read the parent note, you need to see every piece it silently assumes. We build them one at a time, each on top of the last. Nothing is used before it is drawn.

1. A node, and an arrow that points somewhere

The most basic object here is a node — think of it as a labelled dot. We have $n$ of them, numbered $0, 1, 2, \dots, n - 1$ .

Why an array? Because a node is just a number $0 \dots n - 1$ , so parent is a lookup table: "give me a node number, I give you where it points." That single array is the entire data structure.

Look at the picture: every dot has exactly one outgoing arrow (that is the rule — one parent each). The dot whose arrow curls back on itself is the boss.

Definition Initialization — the starting state

Before anything happens, every node is its own boss — $n$ separate one-node sets. So for every $x$ in $0 \dots n - 1$ we set:

for x in range(n):
    parent[x] = x     # each node is its own root
    rank[x]   = 0     # a lone node has height 0

Picture $n$ isolated dots, each with a tiny self-loop arrow. rank[x] = 0 is honest here: a single node really has height $0$ . Every later operation grows outward from this clean slate.

2. What a "set" looks like: a rooted tree

If every node has exactly one parent arrow, and you keep following arrows, you always end at a root (the arrows can't loop anywhere else — only the root loops on itself). That shape has a name.

3. Height, and why we fear it

Walk the figure. On the left is a tall stringy tree: node 3 points to 2, 2 points to 1, 1 points to root 0. To answer "who is 3's boss?" you must follow 3 arrows — the height is $3$ . On the right is a bushy tree: four nodes all point directly at root R, so any find is 1 arrow — height $1$ . Same number of nodes, wildly different cost. This is the villain of the whole story: a straight-line tree (height $= n - 1$ ) makes a single find cost $n - 1$ hops. The two optimizations in the parent note exist entirely to keep this height tiny — short + bushy = good, tall + stringy = bad.

4. `find(x)` — climbing to the boss, and path compression

Now we can read the first operation. find(x) means: start at $x$ , follow parent arrows until you hit a root, return that root.

Why do we need it at all? Because "are $x$ and $y$ in the same group?" becomes simply find(x) == find(y) — compare the two bosses. Two people are teammates if and only if they salute the same captain.

Definition Path compression — rewriting the arrows as you climb

While climbing to the root, we also repoint every node we pass so it aims straight at the root. Next time, those nodes reach the boss in one hop.

def find(x):
    root = x
    while parent[root] != root:   # step 1: climb to the true root
        root = parent[root]
    while parent[x] != root:      # step 2: rewrite every node on the path
        parent[x], x = root, parent[x]
    return root

Step 1 finds the root by following arrows until one loops on itself. Step 2 walks the same path again, and for each node sets parent[node] = root — flattening the chain. The parent note's shorter recursive version does the same thing; the two-pass form above just makes the "rewrite every visited pointer" idea explicit.

Look at the figure: before, 5→4→0 is a chain; after a single find(5), both 5 and 4 point directly at root 0. We paid a little extra now to make every future find cheap — that is exactly why the cost is called amortized (§7).

5. `union(x, y)` — merging, by rank, with a same-set guard

The picture shows the entire operation: we do NOT touch any leaf; we only redirect one boss to bow to another boss. This is why a tree beats a list — a merge is one pointer change. This same "join two groups" motion is what powers Kruskal's Minimum Spanning Tree and Connected Components.

But which root bows to which? And what if $x$ and $y$ are already in the same group? Here is the full procedure.

Definition Union by rank — the full recipe

def union(x, y):
    rx, ry = find(x), find(y)
    if rx == ry:                # GUARD: already same set
        return                  # do nothing — no self-loop, no bogus rank++
    if rank[rx] < rank[ry]:     # make rx the taller (or equal) root
        rx, ry = ry, rx
    parent[ry] = rx             # hang the shorter tree under the taller
    if rank[rx] == rank[ry]:    # only a TIE can make the tree grow
        rank[rx] += 1

How the ranks decide: compare rank[rx] and rank[ry].

If they differ, the larger-rank root wins and the smaller bows to it. The combined height stays $= max$ of the two heights, so no rank changes.
If they are equal, either may be the winner; hanging one equal tree under the other adds one level, so we bump the winner's rank by $1$ .

6. `rank[x]` — a cheap stand-in for height

Formula Why

rank ≥ true height is guaranteed Two facts, together, prove the promise never breaks:

union keeps it true. When roots of different rank merge, the shorter goes under the taller, so the new height $= max (heights) \leq max (ranks) = winner’s rank$ — and we leave the rank unchanged. When equal-rank roots merge, the height rises by exactly $1$ and we raise the rank by exactly $1$ . Either way rank ≥ height still holds.
find (path compression) only lowers the real height — it moves nodes closer to the root, never farther — while leaving rank untouched. So it can only make rank an even looser over-estimate, never a wrong one.

Tiny example. Two rank- $0$ singletons a, b: union(a,b) ties, so parent[b]=a, rank[a]=1. True height is $1$ , rank is $1$ — equal. Now merge in c (rank $0$ ) via union(a,c): ranks differ ( $1 > 0$ ), parent[c]=a, no bump. True height is still $1$ , rank still $1$ . If later a find flattened something, height could drop to $1$ while rank stays $1$ — now rank > height, which is exactly the "loose but safe" state the analysis relies on.

So rank is not a measurement — it is a tie-breaking hint for union that is always at least the true height. Never recompute it downward.

7. Big-O and "amortized" — the language of cost

The parent note talks about $O (n)$ , $O (lo g n)$ , $O (α (n))$ . These describe how the work grows as $n$ grows.

8. The Ackermann function and its inverse $α (n)$

Why does this monster show up? Because the exact cost of path-compression-plus-rank, when analysed carefully, turns out to match the inverse of Ackermann's growth. In practice, treat $α (n)$ as "a constant $\leq 4$ " — that is the whole point.

Putting the pieces together

Read it bottom-up to the box DSU: nodes make trees, trees form a forest with one root each, roots enable find/union, height forces us to invent rank, cost language plus amortized analysis produce the $α (n)$ guarantee — and all of it feeds the parent topic. Related uses branch off toward Graph Cycle Detection and Connected Components.

Equipment checklist

Test yourself — cover the right side and answer out loud.

How do you initialize a fresh DSU on nodes

0 \dots n - 1

For every

x

: parent[x] = x and rank[x] = 0 — each node is its own root, height

0

What does parent[x] == x mean?

x

is a root — the representative/boss of its set.

What is the single array that stores the entire DSU?

parent[], where parent[x] is the one arrow leaving node

x

What is a forest, in this context?

A collection of separate rooted trees — one tree per disjoint set, no root pointing at another.

Why store each set as a tree, not a flat list?

A merge is one pointer change and "same set?" is one climb to the root, instead of scanning lists.

What is a tree's height, in plain words?

The longest chain of parent-arrows from any node up to the root — the worst-case number of hops.

What does find(x) return and how does it know it's done?

The root of

x

's tree; it stops when parent[x] == x.

What does path compression do during a find?

Repoints every node on the climbed path directly at the root, so future finds are one hop.

In union, how do the ranks decide who bows to whom?

The larger-rank root wins; the smaller bows to it. On a tie, either wins and its rank goes up by 1.

Why must union early-return when find(x) == find(y)?

They're already one set; skipping the guard risks a self-loop write or a bogus rank increment that corrupts the structure.

Why is rank always ≥ the true height?

union bumps rank exactly when height rises; path compression only lowers height and never touches rank — so rank can only over-estimate.

What does "amortized

O (α (n))

" mean?

Averaged over a whole sequence of operations, each costs about

α (n) \leq 4

— effectively constant.

What do the two arguments of

A (m, n)

represent?

m

picks how explosive the operation is (add, multiply, power, …);

n

is how many times to apply it.

Why does

α (n)

stay

\leq 4

in practice?

It inverts Ackermann's insanely fast growth, so it grows insanely slowly.