Part V · Trees, Priority Structures and Range Queries
31. Disjoint Set Union (Union-Find)
5 lessons•25 topics•Intermediate / Advanced
5 of 5 lessons published
31.016 animated
DSU model
- Equivalence classes
- Find
- Union
- Connected components
- Representative
- Parent arrays
31.025 animated
Optimizations
- Path compression
- Path halving
- Union by size
- Union by rank
- Inverse Ackermann amortization
31.035 animated
DSU problem patterns
- Number of provinces
- Redundant connection
- Accounts merge
- Kruskal
- Dynamic island additions
31.044 animated
Offline DSU
- Sort queries by weight
- Offline connectivity
- Reverse-delete processing
- Edge activation
31.054 animated
Advanced DSU variants
- Rollback DSU
- Parity DSU
- Weighted/potential DSU
- DSU with metadata
- DSU on tree distinction