Tree & GraphAdvanced
Union-Find
Track disjoint sets using parent pointers with path compression and union by rank for near O(1) operations.
Problem: Number of Connected Components
Given 5 nodes and edges [[0,1], [1,2], [3,4]], find the number of connected components.
Parent Array (index = node, value = parent)
0
1
2
3
4
Initialize: parent[i] = i for all i
Nodes: [0, 1, 2, 3, 4] Edges: [[0,1], [1,2], [3,4]]
Initialize Union-Find
Create parent array where each node is its own parent initially
Step 1/5
Speed:
When to Use
- Connected components
- Detect cycle in undirected graph
- Dynamic connectivity
- Kruskal's MST algorithm
Key Indicators
- Connected components
- Group membership
- Dynamic union/merge
- Redundant connections
Complexity
Time
O(α(n)) ≈ O(1) per operation
Space
O(n)
Common Problems
Number of Connected ComponentsRedundant ConnectionAccounts MergeLongest Consecutive Sequence
Code
parent = [i for i in range(n)]
rank = [0] * n
def find(x):
if parent[x] != x:
parent[x] = find(parent[x]) # path compression
return parent[x]
def union(x, y):
px, py = find(x), find(y)
if rank[px] < rank[py]: px, py = py, px
parent[py] = px
if rank[px] == rank[py]: rank[px] += 1Want all 29 patterns with detailed visual walkthroughs?
The complete book includes 84 practice problems, full decision tree, and illustrated step-by-step solutions.
Book Coming Soon ($4.99)