DFS Post-Order Topological Sort

The second classical topological sort algorithm uses DFS with post-order processing. After fully exploring all neighbours of a node (and their descendants), push the node onto a stack. When all nodes are processed, pop the stack to read the topological order. A node pushed to the stack after all its dependencies means it comes first in the order — so the reversed post-order is the topological sort.

Consider a dependency graph where course A requires course B. When DFS visits A, it first recurses into B. B has no prerequisites, so it finishes first and gets pushed first. Then A finishes and gets pushed. Popping the stack gives A before B in the output — but we reverse at the end, giving B before A: take B first, then A. Post-order pushes dependencies before dependents, so the reversed stack is a valid topological order.