Path Compression + Union by Rank | Inverse Ackermann O(alpha(n)) | Kruskal/Connectivity
Picture a party where everyone arrives in their own group of one. Each time two people realise they share a friend, their two groups merge into a single bigger group. At any moment you might want to do one of two things: merge these two groups, or ask which group is this person in? Union-Find is the data structure built to answer exactly those two questions — and to answer them almost instantly, no matter how many merges have already happened.
To make it concrete, give every element a parent. Follow the parent pointers upward and you always arrive at one special element whose parent is itself — the root, which acts as the name of the whole group. Two elements are in the same group exactly when they reach the same root. So $\text{FIND}(x)$ simply walks up to the root, and $x$ and $y$ are connected when $\text{FIND}(x) = \text{FIND}(y)$. To merge two groups, $\text{UNION}(x,y)$ finds both roots and points one at the other.
Done naively, a long chain of merges can build a tall, skinny tree, and walking to the root grows slow — up to $O(n)$ steps. Two tricks fix that. Union by rank always hangs the shorter tree under the taller one, so trees stay bushy and shallow. Path compression happens during every $\text{FIND}$: after reaching the root, it re-points every node along the path straight to the root, so the next lookup is instant. Used together, the amortised cost per operation is $O(\alpha(n))$, where $\alpha$ is the inverse Ackermann function — a quantity so slow-growing that $\alpha(n) \le 4$ for any $n$ you could ever write down. In practice, each operation is effectively constant time.
In the controls above, the n slider sets how many items the step-by-step trace works through, and the Comparisons and Step counters tick up once per elementary operation — the same way each $\text{FIND}$ or $\text{UNION}$ costs you one unit of work in the analysis.
Try this in the sim above: (1) Press Next one click at a time and watch the Comparisons counter rise by exactly one each step — that is the “one unit per operation” cost you pay for every $\text{FIND}$. (2) Drag n from 4 up to 16 and press Reset; the total Step count grows much faster than $n$, a reminder of how the work can blow up without the rank-and-compression tricks. (3) Set the speed to 0.25x and play, so you can follow each individual step the way you would trace $\text{UNION}$ and $\text{FIND}$ by hand.
| Symbol | Meaning |
|---|---|
| n | Input size (vertices V, edges E, or array length) |
| T(n) | Time complexity function |
| W(n) | Worst-case complexity |
| A(n) | Average-case complexity |
| h | Height or depth of structure |
| k | Number of distinct values / items |
✗ Union-Find gives O(1) per operation.
✓ O(alpha(n)) AMORTIZED with both optimizations. Without union by rank: O(log n). Without path compression: O(log n). Without both: O(n) worst case.
✗ Path compression alone is sufficient for O(alpha(n)).
✓ Both path compression AND union by rank are needed for O(alpha(n)). Path compression alone gives O(log n) amortized. Union by rank alone gives O(log n) per operation.
✗ UNION(x,y) immediately flattens the tree.
✓ UNION merges two trees but doesn't flatten them. Flattening (path compression) happens during FIND operations.
✗ Using union by size instead of union by rank gives different complexity.
✓ Union by size (attach smaller subtree under larger) also gives O(alpha(n)) amortized with path compression. It is equivalent in asymptotic complexity and often easier to implement correctly.
✗ Forgetting to call FIND before UNION -- using raw indices.
✓ Must do rx=FIND(x), ry=FIND(y) before merging. Directly merging parent[x]=y without FIND gives incorrect results when x and y are not roots.
✗ Assuming parent[x]==x means x is isolated (not in any set).
✓ parent[x]==x means x is the ROOT of its set -- it may represent a set with many elements. An isolated singleton also has parent[x]==x. Must track component sizes separately if needed.