Connectivity (DSU and DFS)
You know DFS and Union-Find basics. Now decide which tool fits each problem. Solve Accounts Merge and learn when DSU beats DFS for connectivity.
Lessons
1. Introduction to Connectivity
Can A reach B? Same component?
2. Union-Find with Path Compression and Rank
The data structure
3. DSU vs DFS
Choosing the right tool
4. Problem - Number of Islands II
LC 305 - land appears over time
5. Number of Islands II - Why Naive Fails
Add land, check 4 neighbors
6. Number of Islands II - Setting Up Union-Find
Union-Find on m×n grid
7. Number of Islands II - Transition
Mark land, union neighbors, track count
8. Number of Islands II - Base Cases
Out of bounds, duplicates
9. Number of Islands II - Implementation
idx = r×n + c conversion
10. Number of Islands II - Time and Space
K positions, O(K·α(mn))
11. Problem - Graph Valid Tree
LC 261 - is this a valid tree?
12. Graph Valid Tree - Solution
n-1 edges and no cycle
13. Graph Valid Tree - Why This Works
Edge count + Union-Find cycle check
14. Quiz: Union-Find Applications
DSU vs DFS tradeoffs
15. Quiz: Cycle Detection
When does extra edge create cycle?
16. Common Mistakes in Connectivity
Path compression, union by rank
17. Problem - New Roads Queries
CSES - connectivity queries
18. New Roads Queries - Solution
The solution
19. Problem - Number of Good Paths
LC 2421 - value paths
20. Number of Good Paths - Solution
The solution
21. Problem - Rank Transform of Matrix
LC 1632 - matrix ranking
22. Rank Transform of Matrix - Solution
The solution
23. Problem - Asya and Kittens
CF 1131F - merging groups
24. Asya and Kittens - Solution
The solution
25. Problem - Cows and Snacks
CF 1209D - losing snacks
26. Cows and Snacks - Solution
The solution
27. Section Recap
From accounts merge to edge limits