Topological Sort · DFS-based

A node can only be finalized after everything it points to is done. So push each node onto a stack the moment DFS finishes it, then reverse. Last finished ends up first.

Concept

The idea

Run DFS. When a node has no more unexplored out-edges, it's finished, push it onto a stack. Because you push children before parents, reversing the stack yields a valid topological order.

Finish order → reverse

Recurse into all neighbors first
Push node on the way out (post-order)
Deepest dependencies get pushed earliest
Reverse the finish stack = topo order

Interactive

Watch the finish stack fill

Unvisited On DFS path Finished

Finish stack (push order)

slowfast

Step 0

Finished

Path depth

At node

–

Stacked

Implementation

C++

void dfs(int u, vector<vector<int>>& adj,
         vector<bool>& vis, stack<int>& st) {
    vis[u] = true;
    for (int v : adj[u])
        if (!vis[v]) dfs(v, adj, vis, st);
    st.push(u);                     // push on finish (post-order)
}

vector<int> topoSort(int n, vector<vector<int>>& adj) {
    vector<bool> vis(n, false);
    stack<int> st;
    for (int i = 0; i < n; i++)
        if (!vis[i]) dfs(i, adj, vis, st);

    vector<int> order;
    while (!st.empty()) {           // pop = reverse finish order
        order.push_back(st.top());
        st.pop();
    }
    return order;
}

Complexity

Time

O(V + E)

One DFS traversal; each vertex and edge visited once.

Space

O(V)

Visited array, the finish stack, and recursion depth.

Key insight

post-order

Pushing on exit guarantees dependencies land deeper in the stack.

Notes

DFS vs Kahn's: same result, different mechanics. DFS uses a finish stack; Kahn's uses indegrees and a queue. Pick whichever fits your mental model.
Plain DFS topo sort assumes a DAG. To be safe, add 3-color cycle detection, if you hit a gray node, there's no valid order.
The reversed post-order is exactly why Kosaraju's SCC algorithm reuses this same finish-time trick.
Multiple valid orders exist. Neighbor iteration order decides which one you get.
Recursion can overflow on deep graphs, an explicit stack version avoids it.