Union-Find (Disjoint Sets)

Module 4.13 — Path compression and union by rank

Size:
Union:
Find:

Forest View (8 sets)

0r=01r=02r=03r=04r=05r=06r=07r=0

Parent Array

id=0
p=0
r=0
id=1
p=1
r=0
id=2
p=2
r=0
id=3
p=3
r=0
id=4
p=4
r=0
id=5
p=5
r=0
id=6
p=6
r=0
id=7
p=7
r=0

Activity Log

Union-Find initialized. Each element is its own set.

Complexity

Findα(n) ≈ O(1)
Unionα(n) ≈ O(1)
α(n) = inverse Ackermann, practically constant

Optimizations

Path Compression: During Find, make every node point directly to root. Flattens tree.
Union by Rank: Attach smaller tree under root of larger tree. Keeps height low.

Use Cases

• Kruskal's MST algorithm
• Connected components
• Network connectivity
• Image segmentation