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

==parent[x] == x==. The root is the only node that points to itself; everyone else points to a node strictly closer to the root. This is the loop-stopping test inside find.

A root is any index i with parent[i] == i. Check each: parent[0]=0 ✔, parent[1]=0 ✘, parent[2]=0 ✘, parent[3]=2 ✘, parent[4]=0 ✘. So there is exactly 1 root: node 0. All five nodes are in one set. (Node 2 has rank[2]=1 but is not a root — stale rank on a non-root is allowed and harmless because we only read rank at roots.)

False. Path compression flattens trees, so the true height can be far below rank[r]; rank is only an upper bound we never lower. True height $\le$ rank[r] always.

• union(0,1): roots 0, 1, ranks 0 = 0 (tie). Attach 1 under 0: parent[1]=0, bump rank[0]=1.
• union(2,3): roots 2, 3, ranks 0 = 0 (tie). Attach 3 under 2: parent[3]=2, bump rank[2]=1.
• union(0,2): roots 0, 2, ranks 1 = 1 (tie). Attach 2 under 0: parent[2]=0, bump rank[0]=2.

Final: ==parent = [0,0,0,2], rank = [2,0,1,0]==. Root of everything is 0.

Path from 3: 3 → parent[3]=2 → parent[2]=0 → parent[0]=0 (root found). Root is 0. Full compression re-points every node on the path straight at 0: node 3 and node 2 both become children of 0. Result: ==parent = [0,0,0,0]==. (rank unchanged: [2,0,1,0] — we never touch rank during find.)

The figure below draws this exact tree before and after. Notice in the left panel the coral node 3 sits two hops below root 0 (via node 2); in the right panel the mint nodes 2 and 3 both point straight at 0 — the physical shape the array [0,0,0,0] describes. That flattening is the whole payoff of compression: the next find(3) is a single hop.

This is a perfectly balanced merge, doubling set size each round.

• Round 1 (four ties among rank-0 pairs): four trees of rank 1, each 2 nodes.
• union(0,2): rank 1 = 1 tie → root 0, rank[0]=2 (4 nodes). union(4,6): rank 1 = 1 tie → root 4, rank[4]=2 (4 nodes).
• union(0,4): rank 2 = 2 tie → root 0, rank[0]=3 (8 nodes).

==rank[find(0)] = 3==. This matches the bound: an 8-node balanced tree has rank ${\log }_{2}8=3$.

Induction on r. (Here $r$ is the rank stored at the root — see the "What is $r$" box up top.)

• Base $r=0$: a fresh singleton has $1=2^0$ node. ✔
• Step: a root's rank rises from $r$ to $r+1$ only when two roots of rank exactly $r$ are merged (the tie case). By the inductive hypothesis each had $\ge 2^r$ nodes. The merged tree has $\ge 2^r+2^r=2^{r+1}$ nodes. ✔

$\text{size}(\text{rank-}r\text{ tree})\ge 2^r\Rightarrow 2^r\le n\Rightarrow r\le {\log }_{2}n.$ So the maximum rank (and hence maximum height with union by rank alone) is $\lfloor {\log }_{2}n\rfloor$. For $n=10^6$ that is $\le 19$. See Amortized Analysis for how compression then pushes the amortized cost below this.

By L3.1, rank $\le {\log }_{2}8=3$, so height $\le 3$. This is achievable: pair up singletons into 4 trees of rank 1, pair those into 2 trees of rank 2, pair those into 1 tree of rank 3 — exactly the sequence in L2.3. Height 3 is the maximum. They cannot do better because every rank increase requires two equal-rank subtrees, each already holding $2^r$ nodes; you simply run out of nodes. Height 4 would need $2^4=16>8$ nodes.

Path compression, during a find, re-points visited nodes directly toward the root, physically shortening the tree. But we deliberately do not decrease rank — recomputing true heights would cost as much as the finds we are trying to speed up. So rank[r] may now exceed the actual height. Correctness of merges is unaffected because the merge rule only needs a consistent ordering to decide which tree hangs under which; hanging by an (possibly stale) upper bound still keeps trees shallow, and the classic Amortized Analysis of inverse Ackermann $\alpha (n)$ is built assuming exactly this stale rank. In short: rank guides building, compression fixes reading, and they never conflict.

Keep a size[] array (size[i] = 1 initially). Every node keeps a valid size only as a root.

def union(x, y):
    rx, ry = find(x), find(y)
    if rx == ry:
        return
    if size[rx] < size[ry]:
        rx, ry = ry, rx          # rx is the bigger tree
    parent[ry] = rx              # smaller hangs under bigger
    size[rx] += size[ry]         # bigger absorbs the smaller's count

Advantage: size is exact and cheap to maintain (just add), and it survives path compression perfectly — you may even query it ("how big is my component?") for free. Rank cannot answer that. Both give the same ==$O(\alpha (n))$== amortized cost. Used inside Kruskal's Minimum Spanning Tree and Connected Components identically.

Process edges one at a time. Before adding $(u,v)$, run find(u) and find(v):

• If ==find(u) == find(v)== → u and v are already connected by earlier edges, so this edge closes a loop → cycle. Reject it.
• Otherwise union(u, v) to record that they are now connected.

Why exact: DSU maintains precisely the set of "reachable-so-far" groups. Two nodes share a root iff a path already links them. A new edge between two already-linked nodes must form a cycle (two distinct paths between the same pair). This is the engine of Graph Cycle Detection and the acceptance test in Kruskal's Minimum Spanning Tree.

The figure makes the "already connected" moment concrete: nodes 0, 1, 2 (mint) are one component joined by the solid tree edges (0,1) and (1,2). The dashed coral edge (2,0) is the candidate. Because 2 and 0 already share root 0, this edge would close a loop — so find(2)==find(0) fires and we reject. Vertex 7 (butter) sits alone as its own component, showing the test is local to each set.

Track roots (union by size; ties resolved keeping the first root):

1. (0,1): different → union. Comp: {0,1}.
2. (1,2): different → union. {0,1,2}.
3. (3,4): different → union. {3,4}.
4. (2,0): find(2)=find(0) → REJECT (cycle).
5. (5,6): different → union. {5,6}.
6. (4,5): different → union. {3,4,5,6}.
7. (6,3): find(6)=find(3) → REJECT (cycle).
8. (2,5): find(2)={0,1,2}, find(5)={3,4,5,6} different → union. {0,1,2,3,4,5,6}.

Rejected edges: ==(2,0) and (6,3)== (2 edges). Final components: the big set {0..6} plus the untouched vertex 7 → 2 connected components. See Connected Components.

Path halving uses this loop form:

def find(x):
    while parent[x] != x:
        parent[x] = parent[parent[x]]   # point x at its grandparent
        x = parent[x]                    # then step up to it
    return x

Correctness (it still returns the true root). Consider the ancestor chain of the start node, $x_0\to x_1\to x_2\to \cdots \to r$, where $r$ is the root (the only node with parent[r] == r). Two facts guarantee we end at $r$:

1. The re-pointing line never overshoots the root. Setting parent[x] = parent[parent[x]] replaces $x$'s parent with an ancestor that is strictly closer to $r$ but never past $r$ — because $r$ points to itself, parent[parent[r]] = r, so the pointer of any node can at most become $r$, never something beyond it.
2. The loop stops exactly at $r$. The condition parent[x] != x is true for every non-root and false only at $r$. Since each iteration advances $x$ to a strictly higher ancestor (proved in the halving argument next), $x$ climbs monotonically and must eventually equal $r$, at which point the loop exits and returns $r$. So the returned value is the correct root. ∎

Why the remaining path length at least halves. Number the chain positions $0,1,2,\dots ,k$ from $x_0$ up to $r=x_k$. In one iteration the body does parent[x_j] = x_{j+2} (grandparent) and then x = x_{j+2} — it advances two links per step. Therefore across a single find the pointer visits only positions $0,2,4,\dots$ — every other node — so it performs about $k/2$ iterations instead of $k$. Moreover each visited node $x_j$ now points to $x_{j+2}$ instead of $x_{j+1}$, so on the next find the distance from each of those nodes to the root has been cut down: the path above every visited node is at least halved. Repeatedly applying this drives the tree flat, which — combined with union by rank — is the mechanism behind the ==$O(\alpha (n))$== amortized bound (see Amortized Analysis).

Unfold (each step applies one rule):

• $A(2,2)=A(1,A(2,1))$.
• $A(2,1)=A(1,A(2,0))=A(1,A(1,1))$.
  • $A(1,1)=A(0,A(1,0))=A(0,A(0,1))=A(0,2)=3$.
  • So $A(2,1)=A(1,3)=A(0,A(1,2))$. Now $A(1,2)=A(0,A(1,1))=A(0,3)=4$, so $A(1,3)=A(0,4)=5$. Thus $A(2,1)=5$.
• $A(2,2)=A(1,5)=A(0,A(1,4))$. And $A(1,4)=A(0,A(1,3))=A(0,5)=6$, so $A(2,2)=A(0,6)=7$.

==$A(2,2)=7$==. Notice how even tiny inputs $(2,2)$ demand a deep recursion, and by $A(4,2)$ the value already exceeds the number of atoms in the universe. Because $A$ explodes, its inverse $\alpha (n)$ — "how large must $m$ be so that $A(m,\cdot )$ passes $n$" — barely creeps upward, staying $\le 4$ for any real input. See Ackermann Function.

Design — union by rank + a rollback stack, no compression. Use the non-compressing find (the while version from the top of the page). On each union that actually merges, push a record of exactly the fields it mutated:

history = []   # stack of undo records
 
def find(x):                       # NO compression
    while parent[x] != x:
        x = parent[x]
    return x
 
def union(x, y):
    rx, ry = find(x), find(y)
    if rx == ry:
        history.append(None)       # no-op marker, keeps 1 push per union
        return
    if rank[rx] < rank[ry]:
        rx, ry = ry, rx            # rx is the taller/equal root
    bumped = (rank[rx] == rank[ry])
    history.append((ry, rx, bumped))   # remember what we changed
    parent[ry] = rx
    if bumped:
        rank[rx] += 1
 
def undo():
    rec = history.pop()
    if rec is None:
        return                     # that union was a no-op
    ry, rx, bumped = rec
    parent[ry] = ry                # detach: ry becomes its own root again
    if bumped:
        rank[rx] -= 1              # reverse the rank bump

Why compression must go. Path compression re-points arbitrarily many nodes during a find, and those writes are triggered by reads, not by the union we want to reverse. To undo one union you would have to untangle every compression that touched those nodes since — the number of changed pointers grows with finds, not unions, and they interleave across operations. There is no clean, bounded record to pop. So we keep trees tidy with union by rank alone, which by L3.1 caps height at ${\log }_{2}n$ (recall $n$ = element count). Complexity. With no compression, each find walks a path of length $\le {\log }_{2}n$, so find = ==$O(\log n)$==; union = one find + $O(1)$ pointer work = $O(\log n)$; undo = $O(1)$ (just pop and restore two fields). We lose the $\alpha (n)$ guarantee but gain reversibility. This "DSU with rollback" is the standard tool for offline dynamic-connectivity problems and rests on the Trees and Forests structure staying explicit.

A node is a root iff parent[x] x==. $n$ in "$r\le {\log }_{2}n$" and "$O(\alpha (n))$" denotes the number of elements in the DSU. In "$r\le {\log }_{2}n$", the symbol $r$ denotes the rank stored at a root. $\alpha (n)$ (inverse Ackermann) is ==effectively constant, $\le 4$ for any real input. Rank increases only when two roots of equal rank merge (a tie), and then by 1==. A rank-$r$ tree holds at least ==$2^r$ nodes, so max rank is ${\log }_{2}n$. The cycle test when adding edge (u,v) is find(u) find(v). Rollback DSU must drop path compression, giving ==$O(\log n)$== per op.