DFS-Based Topological Sort

Instead of peeling nodes by in-degree, you can use DFS. Run DFS from each unvisited node. When a node finishes (all descendants explored), push it onto a stack. After all DFS calls complete, the stack holds the topological order.

Why does this work? A node finishes only after all reachable nodes have finished. So if edge $u \to v$ exists, $v$ finishes before $u$, meaning $u$ appears first in the reversed finish order.

To detect cycles, use $3$ colors: white (unvisited), gray (in progress), black (finished). If you visit a gray node, you found a back edge, which means a cycle. This runs in $O(V + E)$ time and uses $O(V)$ space.