Week 38 of 43
CP Track
WEEK 38 LEARNING MODULE
Disjoint Set Union (Union-Find)
Covers Disjoint Set Union (DSU), dynamic connectivity, Path Compression, Union by Rank/Size, Inverse Ackermann complexity $O(\alpha(n))$, and Kruskal's MST / graph cycle detection.
6 Practice Problems4 Core ConceptsVerified Curriculum: high Confidence
What You'll Learn
- ✓Master Disjoint Set Union (DSU / Union-Find) to maintain dynamic partition of disjoint sets.
- ✓Implement `find(x)` with Path Compression (flattening tree structure to point directly to root).
- ✓Implement `union(x, y)` by Rank or Size (attaching smaller tree under larger tree root).
- ✓Understand near-constant amortized complexity: $O(\alpha(n))$ where $\alpha$ is the Inverse Ackermann function.
- ✓Apply DSU to detect cycles in undirected graphs, merge accounts, and evaluate grid connectivity.
Core Concepts
Dynamic Connectivity
O(α(n))Maintaining connected components under incremental edge additions with near-instant query times.
Path Compression
O(α(n)) amortizedDuring find(x), pointing all visited nodes directly to the root, drastically flattening future lookups.
Union by Rank / Size
O(α(n)) amortizedBalancing tree depth by attaching the tree with smaller depth/size under the root of the larger tree.
Graph Cycle Detection via DSU
O(E * α(V))If find(u) == find(v) before adding edge (u, v), adding the edge creates a cycle.
Algorithms Covered
DSU Find with Path CompressionDSU Union by Rank / SizeGraph Cycle DetectionAccounts Merging via DSUGrid Region Cutting via DSU
Data Structures Applied
Disjoint Set Union (Parent & Rank Arrays)
“In Union there is strength.”
— Aesop
Lecture Materials (1)
Official Slide Deck0.8 MB
In Transit
Union Find.pdf
Topic: Union Find
Format: PDF