test_reference_unionfind

Initial state: 8 disjoint elements $\{0\}, \{1\}, \ldots, \{7\}$. Each element is its own parent, all ranks are 0.

Union(0, 1): Both roots have rank 0. Attach 1 under 0 and increment rank of 0.

After Union(0,1): $parent[1] = 0$, $rank[0] = 1$. Set $\{0, 1\}$ formed with root 0.

Union(1, 2): Find(1) = 0 (rank 1), Find(2) = 2 (rank 0). Attach 2 under 0.

After Union(1,2): $parent[2] = 0$. Set $\{0, 1, 2\}$ with root 0.

Union(3, 4): Both roots have rank 0. Attach 4 under 3 and increment rank of 3.

After Union(3,4): $parent[4] = 3$, $rank[3] = 1$. Set $\{3, 4\}$ formed with root 3.

Union(5, 6): Both roots have rank 0. Attach 6 under 5 and increment rank of 5.

After Union(5,6): $parent[6] = 5$, $rank[5] = 1$. Set $\{5, 6\}$ formed with root 5.

Union(6, 7): Find(6) = 5 (rank 1), Find(7) = 7 (rank 0). Attach 7 under 5.

After Union(6,7): $parent[7] = 5$. Set $\{5, 6, 7\}$ with root 5.

Union(2, 3): Find(2) = 0 (rank 1), Find(3) = 3 (rank 1). Equal ranks! Attach 3 under 0, increment rank of 0.

After Union(2,3): $parent[3] = 0$, $rank[0] = 2$. Set $\{0,1,2,3,4\}$ with root 0.

Union(4, 5): Find(4) $\rightarrow$ 3 $\rightarrow$ 0 (rank 2), Find(5) = 5 (rank 1). Attach 5 under 0. Path compression on Find(4)!

After Union(4,5): $parent[5] = 0$. Path compression: $parent[4]$ updated from 3 to 0 directly. All 8 elements now in one set!

Find(7): traverse $7 \rightarrow 5 \rightarrow 0$. Root is 0. Now apply path compression.

Path compression: $parent[7]$ updated from 5 to 0. Future Find(7) returns in $O(1)$.

Final state: all 8 nodes belong to one set with root 0. The $parent[]$ array is nearly flat thanks to path compression.