Card 07/ 07
Recap: Union-Find
Roots, not nodes; rank and compression together; a component count and a cycle test.
Union-find comes down to the five ideas below, each listed with the card that covers it. One rule links them: every operation works on roots, so the cost of everything is the cost of reaching a root.
| The idea | Where |
|---|---|
| Each item stores a parent, and following parents ends at the root, the group's representative; find returns the root and union links two roots | Union-Find: Tracking Which Items Share a Group |
| Each union changes one cell, always a root's; counting the cells that hold their own index counts the groups | Trace Union and Find on a Parent Array |
| Setting the parent of the named item instead of its root cuts it from its group, so union calls find on both arguments | Linking the Nodes Instead of Their Roots |
| Union by rank keeps trees within log₂ n, path compression flattens every path find walks, and only together do they give O(α(n)) amortised | Union by Rank and Path Compression |
| A component count falls on each successful union, and a union that finds one root for both ends has found an edge that closes a cycle | Union-Find in Python, Java and TypeScript |
The costs below are for n items. The gap between the columns is the gap between a chain and a tree no taller than log₂ n that every find flattens, and α(n) stays at 4 or below for any n that fits in memory.
| Operation | Without optimisations | With rank and compression |
|---|---|---|
| find(x) | O(n) | O(α(n)) amortised |
| union(a, b) | O(n) | O(α(n)) amortised |
| Are a and b in one group? | O(n) | O(α(n)) amortised |
| Memory | O(n) | O(n) |
Together they let you trace union and find on a parent array by hand, write the structure with both optimisations in any of the three languages, and use it to count the connected components of an undirected graph and to find the edge that closes a cycle.
← → move through sections and cards