Pattern Recognition Drill
Medium Advanced Graphs
The Problem
Return a topological ordering of a DAG.
What approach would you use?
Think about it before scrolling down.
Kahn's: queue nodes with in-degree 0. Process, reduce neighbors' in-degrees. Add newly zero-degree nodes. O(V+E).
DFS post-order reversed gives topological order. Also O(V+E).
Common Trap
If result has fewer than V nodes, the graph has a cycle (not a DAG).