Mixed Practice: Advanced Graphs
Test your ability to recognize which graph algorithm to apply. Problems spanning flow, matching, SCCs, and more.
Lessons
1. Intro
What this practice section covers.
2. Decision Framework
How to choose the right algorithm.
3. Pattern: SCC Applications
When to use strongly connected components.
4. Pattern: 2-SAT
When to use 2-SAT.
5. Pattern: Functional Graphs
When each node has exactly one outgoing edge.
6. Pattern: Hamiltonian vs Euler
Visiting vertices vs visiting edges.
7. Problem - Coin Collector
CSES 1686 - SCC and DP.
8. Coin Collector - Analysis
Recognizing the SCC pattern.
9. Coin Collector - Implementation
Code walkthrough.
10. Problem - Giant Pizza
CSES 1684 - 2-SAT.
11. Giant Pizza - Analysis
Recognizing the 2-SAT pattern.
12. Giant Pizza - Implementation
Code walkthrough.
13. Problem - Planets Queries II
CSES 1160 - Functional graphs.
14. Planets Queries II - Analysis
Recognizing the functional graph pattern.
15. Planets Queries II - Implementation
High-level approach.
16. Problem - Hamiltonian Flights
CSES 1690 - Bitmask DP.
17. Hamiltonian Flights - Analysis
Recognizing the bitmask DP pattern.
18. Hamiltonian Flights - Implementation
Code walkthrough.
19. Problem - Knight's Tour
CSES 1689 - Backtracking.
20. Knight's Tour - Analysis
Backtracking with heuristics.
21. Knight's Tour - Implementation
Code walkthrough.
22. Quiz: Pattern Recognition
Knowledge check
23. Common Mistakes
Pitfalls in pattern recognition.
24. Section Recap
Summary of pattern recognition.