1. One-Liner
Path compression makes find flatten the tree: every visited node’s parent becomes the root directly.
2. The Problem It Solves
After many unions, paths get long; path compression shortens future finds—this is what gives inverse-Ackermann amortized complexity with rank.
3. The Core Idea
Recursive or iterative find: set parent[x] = find(parent[x]) before returning; first traversal pays, later hops are O(1) to root.
4. How It Works (Step-by-Step)
| Step | Action |
|---|---|
| 1 | On find(x), if parent[x]!=x, recurse/iterate |
| 2 | Set parent[x] to root after finding root |
| 3 | Return root id |
| 4 | Combine with union-by-rank for theory bounds |
5. Dry Run Example
Chain 0→1→2→3: first find(0) walks and flattens so 0,1,2 point to 3; next find(0) is one hop.
6. Key Properties
| Property | Detail |
|---|---|
| Amortized | α(n) with rank |
| Single find | Still proportional to old path length once |
| Iterative | Path halving variant also exists |
7. Where It Is Used
| Domain / System | Use |
|---|---|
| MST / connectivity | Industry DSU |
| Image labeling | Union pixels |
| Social graphs | Component queries |
8. Interview Tips
Mention two-pass iterative find if avoiding recursion stack. Pair with union by rank for standard proof.
9. Comparison with Other Algorithms
| Technique | Notes |
|---|---|
| No compression | Weaker bounds |
| Path splitting | Older heuristic |
| Link-cut tree | Dynamic trees beyond DSU |
10. Complexity
| -- | -- |
|---|---|
| Time | O(α(n)) amortized find/union together |
| Space | O(n) |
Implementation Example (PYTHON)
class UnionFind:
def __init__(self, n):
self.p = list(range(n))
self.r = [0] * n
def find(self, x):
if self.p[x] != x:
self.p[x] = self.find(self.p[x])
return self.p[x]
def union(self, a, b):
ra, rb = self.find(a), self.find(b)
if ra == rb:
return False
if self.r[ra] < self.r[rb]:
ra, rb = rb, ra
self.p[rb] = ra
if self.r[ra] == self.r[rb]:
self.r[ra] += 1
return True