Pattern Recognition Drill
Medium Advanced Graphs
The Problem
Can all courses be completed given prerequisites? (Cycle detection in DAG.)
What approach would you use?
Think about it before scrolling down.
Run Kahn's algorithm. If all nodes are processed, no cycle → all courses completable. O(V+E).
DFS with 3-color marking (white/gray/black). Gray→Gray edge = cycle. O(V+E).
Common Trap
This IS a cycle detection problem in disguise. Model courses as a directed graph.