Disjoint Set Union (DSU)
Union by rank/size, path compression, rollback DSU, and applications.
Lessons
1. Intro
Dynamic changes
2. Disjoint Set Union (DSU)
The Structure
3. The Intuition - Leaders
Who is the boss?
4. The Parent Array
Tracking relationships
5. The Find Operation
Finding the Leader
6. The Union Operation
Merging Groups
7. The Problem with Naive DSU
Long Chains
8. Improvement 1 - Path Compression
The Magic Step
9. Implementation - Find with Compression
Coding the Magic
10. Quiz: Path Compression
Knowledge check
11. Improvement 2 - Union by Size
Balancing the Tree
12. Implementation - Union by Size
Coding the Merger
13. The Full DSU Template
Copy-Paste Ready
14. Cycle Detection
Application 1
15. Quiz: Cycle Detection with DSU
Knowledge check
16. LeetCode 684 Redundant Connection - Problem Statement
LeetCode 684
17. LeetCode 684 Redundant Connection - Logic
First Hit
18. Counting Components
Application 2
19. LeetCode 547 Number of Provinces - Problem Statement
LeetCode 547 (DSU Version)
20. LeetCode 547 Number of Provinces - Strategy
Iterating the Matrix
21. Tracking Component Sizes
Application 3
22. CSES 1676 Road Construction - Problem Statement
CSES Problem Set
23. CSES 1676 Road Construction - Logic
Maintaining State
24. Pattern - Logic & Equations
Symbols as Nodes
25. Quiz: Component Counting
Knowledge check
26. LeetCode 990 Satisfiability of Equality Equations - Problem Statement
LeetCode 990
27. LeetCode 990 Satisfiability of Equality Equations - Strategy
Two Passes
28. Pattern - Transitivity
Swapping Logic
29. LeetCode 1202 Smallest String With Swaps - Problem Statement
LeetCode 1202
30. LeetCode 1202 Smallest String With Swaps - Algorithm
Sorting Components
31. Pattern - Indirect Grouping
Mapping Data
32. LeetCode 721 Accounts Merge - Problem Statement
LeetCode 721
33. LeetCode 721 Accounts Merge - The Graph
Emails are Edges
34. Pattern - Grid Components
Connecting pixels
35. Quiz: Indirect Grouping
Knowledge check
36. LeetCode 827 Making A Large Island - Problem Statement
LeetCode 827
37. LeetCode 827 Making A Large Island - Logic
DSU + Virtual Flip
38. Pattern - Hub Nodes
Reducing Edges
39. Codeforces 1263D Secret Passwords - Problem Statement
Codeforces 1263D
40. Codeforces 1263D Secret Passwords - Logic
Letters are Hubs
41. Pattern - Offline Queries
Reordering Time
42. Quiz: Offline Processing
Knowledge check
43. LeetCode 1697 Edge Limited Paths - Problem Statement
LeetCode 1697
44. LeetCode 1697 Edge Limited Paths - Implementation Plan
Sorting Everything
45. Pattern - The Reverse Time Trick
Destruction is hard
46. USACO 644 Closing the Farm - Problem Statement
USACO Gold
47. USACO 644 Closing the Farm - Solution
Adding Barns
48. Quiz: Reverse Time Trick
Knowledge check
49. Section Recap
Dynamic Connectivity