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

Before reading any example, keep these two code skeletons in view — every trace below is just these lines running:

The scenario matrix

Every DSU trace is built from a small set of case classes. If you cover all of them, you have covered DSU. Here they are:

#	Case class	What triggers it	Which code branch
A	Equal-rank union	both roots have same `rank`	tie → `rank[rx] += 1`
B	Unequal-rank union	one root taller	hang smaller, no rank bump
C	Union with self / already-same	`find(x) == find(y)`	early `return`
D	Degenerate single node	set of size 1, rank 0	`parent[x] == x` immediately
E	Long chain + path compression	many finds down a deep tree	compression rewrites `parent[]`
F	Word problem — connectivity	"are these two connected?"	repeated `same()`
G	Kruskal MST	edges sorted by weight, accept if roots differ	union on accept, skip on same
H	Cycle detection	undirected edge whose endpoints already share a root	detect via case C

The eight examples below hit all eight cells. Where geometry (the tree shape) matters, a figure carries it.

Example 1 — Equal-rank union (cell A)

Worked example The tie that raises the tree

Start fresh with elements ${0, 1}$ : parent=[0,1], rank=[0,0]. Run union(0,1).

Forecast: Guess before reading — after the union, what is rank[0]? Does the height of the tree grow?

Step 1. rx = find(0) = 0, ry = find(1) = 1. Why this step? union always finds both roots first, because we merge sets, not the two named elements. Both are roots already (parent[0]==0, parent[1]==1), so no climbing.

Step 2. Compare ranks: rank[0] == rank[1] == 0. This is a tie, so no swap is forced; keep rx=0. Why this step? The swap in the code only fires when rank[rx] < rank[ry]. On a tie we skip it.

Step 3. parent[1] = 0 — hang $1$ under $0$ . Why this step? One root must become a child of the other; the choice is arbitrary on a tie.

Step 4. Because ranks were equal, bump: rank[0] += 1 → rank[0] = 1. Why this step? Two rank-0 trees each had height 0; stacking one under the other makes height 1. The rank must record this growth — this is the only way a tree ever gets taller. Look at the figure: the height genuinely went from 0 to 1.

Verify: Final parent=[0,0], rank=[1,0]. Rank bound says a rank-1 tree has $\geq 2^{1} = 2$ nodes — we have exactly 2. ✔ Consistent with the forest view: one tree, root 0.

Example 2 — Unequal-rank union: the short bows to the tall (cell B)

Worked example Hanging without growing

After Example 1 we have tree $T$ : root $0$ , child $1$ , rank[0]=1. Now add a fresh singleton $2$ (parent[2]=2, rank[2]=0) and run union(0,2).

Forecast: Will rank[0] become 2? Or stay 1?

Step 1. rx = find(0) = 0 (rank 1), ry = find(2) = 2 (rank 0). Why this step? Standard — resolve to roots first.

Step 2. rank[rx]=1 is not < rank[ry]=0, so no swap. rx stays the taller root $0$ . Why this step? We want the taller tree to stay on top so the combined height is just the taller height. The swap line guarantees rx is the taller/equal root before we attach.

Step 3. parent[2] = 0. Why this step? Hang the rank-0 tree ( $2$ ) under the rank-1 tree ( $0$ ).

Step 4. Ranks were unequal (1 != 0), so no rank bump. Why this step? Node $2$ becomes a child at depth 1 — it fits inside the height the tree already had. The tallest path is still $0 \to 1$ (length 1). Height did not grow, so rank must not grow. See figure: $2$ slots in beside $1$ , nothing gets deeper.

Verify: parent=[0,0,0], rank=[1,0,0]. Rank-1 tree needs $\geq 2$ nodes; we have 3. ✔ Bound is a lower bound on size, so 3 ≥ 2 is fine.

Example 3 — Union with self / already-same set (cell C)

Worked example The no-op that protects the structure

Using the tree from Example 2 (parent=[0,0,0], rank=[1,0,0]), run union(1,2).

Forecast: $1$ and $2$ are already in the same set. What should union do — nothing, or corrupt something?

Step 1. rx = find(1): parent[1]=0, parent[0]=0 → root is $0$ . ry = find(2): parent[2]=0 → root is $0$ . Why this step? Both climb to the same root.

Step 2. rx == ry == 0 → return immediately. Why this step? This is the guard from the parent note's mistake box. Skip it and Step 3 would run parent[0] = 0 (harmless) or, worse, if the swap had fired, bump a rank for a merge that never happened — corrupting the invariant. Early-return is mandatory.

Verify: parent and rank are unchanged: parent=[0,0,0], rank=[1,0,0]. A union of a set with itself must be a no-op. ✔

Example 4 — Degenerate single node (cell D)

Example 5 — Long chain, then path compression flattens it (cell E)

Worked example From a stick to a star

Suppose an adversary built a chain without union-by-rank: parent=[0,0,1,2,3] for elements ${0, 1, 2, 3, 4}$ . So $4 \to 3 \to 2 \to 1 \to 0$ , a stick of height 4. Run the recursive find(4).

Forecast: After this single find(4), how many nodes point directly at root $0$ ?

Step 1. find(4): parent[4]=3 != 4, so recurse find(3). find(3) → recurse find(2) → recurse find(1) → find(0). Why this step? We must reach the root to know the answer. The recursion unwinds from the bottom (root) upward.

Step 2. find(0) returns $0$ (it is the root). Now each returning frame executes parent[x] = find(parent[x]) = the root: parent[1]=0, parent[2]=0, parent[3]=0, parent[4]=0. Why this step? The recursion knows the root, so it repoints every visited node straight at $0$ . This is full path compression — the whole path collapses. See the before/after figure: the stick becomes a star.

Step 3. Now find(4) costs 1 hop (parent[4]=0, and 0 is root). Same for $1, 2, 3$ . Why this step? This is the amortized payoff: one expensive walk pays for many cheap future ones — the mechanism behind $O (α (n))$ .

Verify: After find(4): parent=[0,0,0,0,0]. All five point to $0$ ; tree height dropped from 4 to 1. ✔

Example 6 — Full mixed trace on ${0..5}$ (cells A + B + E together)

Worked example Building six elements from scratch

parent=[0,1,2,3,4,5], rank=[0,0,0,0,0,0]. Run in order: union(0,1), union(2,3), union(0,2), union(4,5), union(0,4), then find(5).

Forecast: What is the final rank of root $0$ , and after find(5) who does $5$ point to directly?

Step 1. union(0,1): equal rank (0,0) → parent[1]=0, rank[0]=1. (cell A) Step 2. union(2,3): equal rank → parent[3]=2, rank[2]=1. (cell A) Step 3. union(0,2): rank[0]=1, rank[2]=1, equal → parent[2]=0, rank[0]=2. (cell A) Why this step? Two rank-1 trees merged → the winner's rank climbs to 2. This is the only moment rank 2 appears. Step 4. union(4,5): equal → parent[5]=4, rank[4]=1. (cell A) Step 5. union(0,4): rank[0]=2 > rank[4]=1 → no swap needed (rx=0 already taller), parent[4]=0, no bump. (cell B) Why this step? Unequal ranks: $4$ 's subtree fits under $0$ without deepening. Rank stays 2. Step 6. find(5): path $5 \to 4 \to 0$ . Compression sets parent[5]=0. (cell E) Why this step? Future find(5) becomes one hop.

Verify: Final rank[0]=2; a rank-2 tree needs $\geq 2^{2} = 4$ nodes and we have all 6. parent after find(5): parent=[0,0,0,2,0,0]. ✔ (Note $3$ still points to $2$ because we never find(3).)

Example 7 — Word problem: friend network connectivity (cell F)

Worked example Can Ava reach Finn?

Six people numbered $0$ – $5$ : Ava $= 0$ , Bo $= 1$ , Cy $= 2$ , Di $= 3$ , Eve $= 4$ , Finn $= 5$ . Friendships (undirected edges) arrive: $(0, 1), (2, 3), (1, 2), (4, 5)$ . Question: is Ava ( $0$ ) in the same friend-group as Finn ( $5$ )? And as Di ( $3$ )?

Forecast: Two edges connect the block ${0, 1, 2, 3}$ ; ${4, 5}$ is separate. Guess the two answers.

Step 1. Model each friendship as union. Groups of friends are exactly the connected components — this is the connected-components use of DSU. union(0,1), union(2,3), union(1,2) merge ${0, 1}$ and ${2, 3}$ into ${0, 1, 2, 3}$ ; union(4,5) builds ${4, 5}$ . Why this step? DSU turns "who is reachable from whom" into "who shares a root", answerable in near-constant time.

Step 2. same(0,5) = (find(0) == find(5)). Root of $0$ is in the big block; root of $5$ is in ${4, 5}$ — different → False. Why this step? No chain of friendships links the two blocks, so no shared root.

Step 3. same(0,3): both in ${0, 1, 2, 3}$ → same root → True. Why this step? $0 - 1 - 2 - 3$ is one connected component.

Verify: same(0,5)=False, same(0,3)=True. Two components: ${0, 1, 2, 3}$ and ${4, 5}$ , sizes $4 + 2 = 6$ = total people. ✔

Example 8 — Kruskal MST + a cycle rejected (cells G + H)

Worked example Building a minimum spanning tree, skipping the cycle edge

Graph on vertices ${0, 1, 2, 3}$ with weighted edges: $(0, 1, w = 1), (1, 2, w = 2), (0, 2, w = 3), (2, 3, w = 4)$ . Run Kruskal: sort edges by weight, accept an edge iff its endpoints are in different sets, else it would form a cycle.

Forecast: Which single edge gets rejected, and what is the total MST weight?

Step 1. Sort by weight: already $1, 2, 3, 4$ . Start each vertex in its own set (four singletons — four rank-0 trees). Why this step? Kruskal processes cheapest edges first; DSU tracks which vertices are already joined.

Step 2. Edge $(0, 1, 1)$ : find(0)≠find(1) → accept, union(0,1). MST weight $= 1$ . (cell G — accept) Step 3. Edge $(1, 2, 2)$ : roots differ → accept, union(1,2). Now ${0, 1, 2}$ joined. Weight $= 1 + 2 = 3$ . Step 4. Edge $(0, 2, 3)$ : find(0) == find(2) (both in ${0, 1, 2}$ ) → reject. (cell H — cycle detected) Why this step? Adding $(0, 2)$ would connect two vertices already connected → a cycle. DSU's early-same test is exactly cycle detection: same root ⇒ this edge closes a loop. Step 5. Edge $(2, 3, 4)$ : roots differ → accept, union(2,3). Weight $= 3 + 4 = 7$ . All 4 vertices joined with $4 - 1 = 3$ edges. Why this step? A spanning tree on $n$ vertices has exactly $n - 1$ edges; we stop when connected.

Verify: Rejected edge $= (0, 2)$ ; MST edges $= {(0, 1), (1, 2), (2, 3)}$ ; total weight $= 1 + 2 + 4 = 7$ ; edge count $= 3 = n - 1$ . ✔

Recall Which cell did each example cover?

Cover the right side and recite. Example 1 ::: A — equal-rank union, rank bumps by 1. Example 2 ::: B — unequal-rank union, no rank bump. Example 3 ::: C — already-same set, early return no-op. Example 4 ::: D — degenerate singleton, zero climbs. Example 5 ::: E — long chain flattened by path compression. Example 6 ::: A + B + E — full mixed six-element trace. Example 7 ::: F — connectivity word problem (components). Example 8 ::: G + H — Kruskal accept/reject + cycle detection.

Flashcards

In union, when does rank increase?

Only on a tie (equal ranks) — then the surviving root's rank

+ = 1

After find(4) on chain

4 \to 3 \to 2 \to 1 \to 0

with full compression, what is parent?

[0,0,0,0,0] — every node points straight at root 0.

Why does union(x,y) early-return when roots are equal?

The sets are already merged; proceeding could corrupt parent pointers or wrongly bump a rank.

In Kruskal, when is an edge rejected?

When its two endpoints already share a root (find(u)==find(v)) — accepting it would form a cycle.

How many edges does an MST on

n

vertices have?

Exactly

n - 1