DSU Ladder¶
DSU practice should build fast instinct for “merge-only connectivity” problems and teach when component metadata still fits the DSU model.
Who This Is For¶
Use this ladder if:
- you know the structure, but not yet the modeling cues
- you still hesitate between DFS/BFS and DSU on connectivity tasks
- Kruskal feels like a memorized recipe instead of a natural reduction
Warm-Up¶
- static connectivity
- count connected components
- cycle detection in an undirected graph
Target skill:
- see connected components as mergeable sets
Core¶
- Kruskal
- component sizes and metadata
- offline connectivity with only additions
Target skill:
- attach useful component data safely to roots only
Stretch¶
- parity constraints
- rollback DSU -> DSU Rollback / Offline Dynamic Connectivity ladder
- dynamic connectivity in offline form -> Dynamic Connectivity
- C11XU
Target skill:
- understand the limits of plain DSU and when variants appear
Retrieval Layer¶
- exact quick sheet -> DSU hot sheet
- merge-only connectivity starter -> dsu-basic.cpp
- compare against Kruskal usage -> Road Reparation
- rollback / deletion compare lane -> DSU Rollback hot sheet
Exit Criteria¶
You are ready to move on when:
- you can implement
findandunitefrom memory - you know why path compression and union by size help
- you can tell when deletions make plain DSU the wrong tool