1. One-Liner
Union-Find maintains a partition of items into disjoint sets and supports find (which set?) and union (merge two sets).
2. The Problem It Solves
You need to know if two nodes are in the same connected component after adding edges, or count components—classic in Kruskal-style processing and offline connectivity.
3. The Core Idea
Each element points to a parent; the set is a tree. Find walks to the root. Union hangs one root under another—simple but trees can skew.
4. How It Works (Step-by-Step)
| Step | Action |
|---|---|
| 1 | Initialize parent[i]=i for all i |
| 2 | find(x): walk until parent[x]==x |
| 3 | union(a,b): if find(a)==find(b), skip; else parent[ra]=rb |
| 4 | Optionally track component count on successful union |
5. Dry Run Example
Elements 0..3, unions (0,1), (2,3), then (1,2): after first two steps roots {0,1} and {2,3}; third merges all—one component.
6. Key Properties
| Property | Detail |
|---|---|
| Correctness | Same root ⇔ same set |
| Tree shape | Can degenerate to a chain |
| Ops | find + union per edge |
7. Where It Is Used
| Domain / System | Use |
|---|---|
| Networking | Connected subnets |
| Kruskal | Edge sort + DSU cycle check |
| Games | Guild / alliance merging |
8. Interview Tips
State without rank/path compression: amortized is weaker. Know when union order matters; mention optimizations in follow-up.
9. Comparison with Other Algorithms
| Technique | Notes |
|---|---|
| List + DFS | Slower dynamic connectivity |
| Union by rank | Shorter trees |
| Adjacency matrix BFS | Overkill for connectivity only |
10. Complexity
| -- | -- |
|---|---|
| Time | Nearly O(n) worst-case find per op without extras |
| Space | O(n) parent array |
Implementation Example (PYTHON)
class UnionFind:
def __init__(self, n):
self.parent = list(range(n))
def find(self, x):
while self.parent[x] != x:
x = self.parent[x]
return x
def union(self, a, b):
ra, rb = self.find(a), self.find(b)
if ra == rb:
return False
self.parent[ra] = rb
return True