CSE201, Winter 2025, Lec 5: DAGs, topological sort, and DFS
C. Seshadhri · 76:58
DFS gives an \(O(n+m)\) test for whether a directed graph is a DAG (any DFS forest has no back edge) and, when it is a DAG, a topological order from the same run: reverse finish-time order, recorded by pushing vertice...