DFS Topo Sort

Post-Order Is the Secret Weapon

Here's a non-obvious claim: if you run DFS on a DAG and record each node when you finish it (not when you discover it), then reverse that list, you get a valid topological order. Every time.

Understanding why this works gives you a tool that extends far beyond topological sort -- into SCC detection, 2-SAT, and any problem that needs "process things in dependency order."

---

The Core Idea

When DFS finishes processing a node u, every node reachable from u has already been finished and added to the list. So u appears after all its descendants in the post-order list. Reversing puts u before all its descendants. That's exactly what topological order requires.

void dfs(int u) {
    color[u] = 1; // GRAY: in progress
    for (int v : adj[u]) {
        if (color[v] == 0) dfs(v);
        else if (color[v] == 1) has_cycle = true;
        if (has_cycle) return;
    }
    color[u] = 2; // BLACK: done
    order.push_back(u); // post-order
}

After calling dfs from every unvisited node, reverse order. That's your topological sort.

💡 Key insight. Post-order in DFS means "I finished after everything I depend on finished." Reversing turns that into "I appear before everything that depends on me."

---

Three-Color Cycle Detection

Undirected cycle detection uses a parent check. Directed cycle detection needs more -- it needs to distinguish between three states:

Color	Meaning	What it tells you
WHITE (0)	Unvisited	Haven't touched this node yet
GRAY (1)	In current DFS path	Currently on the recursion stack
BLACK (2)	Fully processed	Done with this node and all descendants

The rule: If you're at node u and encounter a GRAY neighbor v, then v is an ancestor of u on the current path. The path from v to u plus the edge u -> v forms a cycle.

Encountering a BLACK node is harmless. It means v was fully processed in an earlier DFS branch. There's no cycle through that edge.

⚠ Gotcha. In directed graphs, you CANNOT use the simple "visited and not parent" check from undirected cycle detection. A visited node might be BLACK (fully processed from another branch), not part of your current path. Only GRAY nodes indicate cycles.

---

Full Trace with Colors

Consider this 6-node DAG:

1 → 2 → 4
1 → 3 → 4
3 → 5 → 6

Adjacency list: 1:[2,3], 2:[4], 3:[4,5], 4:[], 5:[6], 6:[]

Step	Call	Action	Colors (1-6)	Post-Order
1	dfs(1)	Mark 1 GRAY, visit 2	G W W W W W	[]
2	dfs(2)	Mark 2 GRAY, visit 4	G G W W W W	[]
3	dfs(4)	Mark 4 GRAY, no neighbors	G G W G W W	[]
4	dfs(4)	Mark 4 BLACK, push 4	G G W B W W	[4]
5	dfs(2)	Mark 2 BLACK, push 2	G B W B W W	[4, 2]
6	dfs(1)	Visit 3	G B W B W W	[4, 2]
7	dfs(3)	Mark 3 GRAY, visit 4 (BLACK, skip)	G B G B W W	[4, 2]
8	dfs(3)	Visit 5	G B G B W W	[4, 2]
9	dfs(5)	Mark 5 GRAY, visit 6	G B G B G W	[4, 2]
10	dfs(6)	Mark 6 GRAY→BLACK, push 6	G B G B G B	[4, 2, 6]
11	dfs(5)	Mark 5 BLACK, push 5	G B G B B B	[4, 2, 6, 5]
12	dfs(3)	Mark 3 BLACK, push 3	G B B B B B	[4, 2, 6, 5, 3]
13	dfs(1)	Mark 1 BLACK, push 1	B B B B B B	[4, 2, 6, 5, 3, 1]

Post-order: [4, 2, 6, 5, 3, 1]

Reversed: 1, 3, 5, 6, 2, 4

Check: every edge goes left-to-right in this order. Valid topological sort.

Notice step 7: node 3 sees node 4, which is BLACK. This is fine -- it's not on the current path. No cycle.

---

Cycle Detection Trace

Now add edge 4 → 1 to create a cycle.

Step	Call	Action	Colors (1-4)	Result
1	dfs(1)	Mark 1 GRAY, visit 2	G W W W	--
2	dfs(2)	Mark 2 GRAY, visit 4	G G W W	--
3	dfs(4)	Mark 4 GRAY, visit 1	G G W G	--
4	dfs(4)	Node 1 is GRAY!	G G W G	CYCLE

Node 4 sees node 1, which is GRAY. That means 1 is on the current path: 1 → 2 → 4 → 1. Cycle found.

---

CSES Round Trip II -- Extracting the Cycle

The problem asks: given a directed graph, find a cycle and print it, or report that none exists.

Detection is step one. Extraction requires tracking parents:

int par[200005];
int cycleStart = -1, cycleEnd = -1;

void dfs(int u) {
    color[u] = 1;
    for (int v : adj[u]) {
        if (color[v] == 1) {
            cycleStart = v;
            cycleEnd = u;
            return;
        }
        if (color[v] == 0) {
            par[v] = u;
            dfs(v);
        }
        if (cycleStart != -1) return;
    }
    color[u] = 2;
}

When you find cycleStart and cycleEnd, walk back through par[]:

vector<int> cycle;
cycle.push_back(cycleStart);
for (int v = cycleEnd; v != cycleStart; v = par[v])
    cycle.push_back(v);
cycle.push_back(cycleStart);
reverse(cycle.begin(), cycle.end());

For our cycle 1 → 2 → 4 → 1 (cycleStart = 1, cycleEnd = 4):

Walk	Current	par[current]	Path
Start	--	--	[1]
1	4	2	[1, 4]
2	2	1	[1, 4, 2]
Stop	1 == cycleStart	--	[1, 4, 2, 1]

Reversed: 1 → 2 → 4 → 1.

---

Kahn's vs DFS Topo Sort

Aspect	Kahn's (BFS)	DFS
Style	Iterative	Recursive
Cycle detection	order.size() < n	GRAY node encountered
Cycle extraction	Harder (nodes with remaining in-degree)	Natural (parent chain)
Stack overflow	No risk	Risk on deep graphs
Complexity	O(V + E)	O(V + E)

Both are O(V + E). Both produce valid topological orderings. In practice:

• Use Kahn's when you just need any valid ordering and want simple, iterative code.
• Use DFS when you need to extract cycles or when the problem naturally involves DFS (SCC, etc.).

💡 Key insight. Kahn's peels nodes from the "outside in" (no-dependency nodes first). DFS drills from the "inside out" (deepest dependencies first, then reverses). Same result, opposite direction.

---

LC 802 -- Find Eventual Safe States

A node is "safe" if every path starting from it leads to a terminal node (a node with out-degree 0). Equivalently, a node is safe if it's NOT part of a cycle and NOT reachable to a cycle.

Run three-color DFS. After DFS completes: - BLACK nodes are safe. - GRAY nodes (stuck in cycles) are unsafe.

vector<int> eventualSafeNodes(vector<vector<int>>& graph) {
    int n = graph.size();
    vector<int> color(n, 0);
    vector<int> result;

    function<bool(int)> dfs = [&](int u) -> bool {
        color[u] = 1;
        for (int v : graph[u]) {
            if (color[v] == 1) return false;
            if (color[v] == 0 && !dfs(v)) return false;
        }
        color[u] = 2;
        return true;
    };

    for (int i = 0; i < n; i++) {
        if (color[i] == 0) dfs(i);
        if (color[i] == 2) result.push_back(i);
    }
    return result;
}

---

Try It

The starter code has the DFS skeleton. Fill in the cycle detection and post-order push.

Test case 1 -- DAG:

Input:
5 5
1 2
1 3
2 4
3 4
4 5

Output:
1 3 2 4 5
(or any valid topological order)

Test case 2 -- cycle:

Input:
3 3
1 2
2 3
3 1

Output:
IMPOSSIBLE

Challenge: Modify the code to print the actual cycle when one is detected, not just "IMPOSSIBLE."

---

Problems

Problem	Link	Difficulty
CSES Round Trip II	cses.fi/problemset/task/1678	Medium
LC 207 — Course Schedule	leetcode.com/problems/course-schedule	Medium
LC 802 — Find Eventual Safe States	leetcode.com/problems/find-eventual-safe-states	Medium