Day 12 · Week 3

DFS Topological Sort & Cycle Detection

Level 4 · Topological Sort · 2 hrs: ~45 min theory · ~60 min code · ~15 min notes

🧠 Mental Model

A vertex's DFS finish time encodes dependency order: a vertex finishes only after all its descendants finish. So listing vertices by decreasing finish time (i.e. pushing each to a stack in post-order and reversing) yields a topological order. Cycle detection rides along via three-color marking.

Where Kahn's peels from the front (sources), DFS-topo builds from the back (sinks finish first). Both are correct; DFS-topo is terser and composes with other DFS bookkeeping.

⚙️ Mechanics — Post-order + Reverse

DFS from every unvisited vertex.
After a vertex's recursion returns (all descendants done), push it to a stack.
Pop everything → topological order.

Three-Color Cycle Detection

Directed cycles can't be found by a simple visited set — you must distinguish "currently on the recursion stack" from "fully done."

Color	Meaning
White (0)	Unvisited.
Gray (1)	In progress — on the current DFS stack.
Black (2)	Finished — fully explored.

Back-edge = cycle: encountering a gray vertex during DFS means you've looped back to an ancestor still on the stack — a directed cycle. A black neighbor is fine (already done, no cycle).

📐 Correctness

Theorem (finish-time ordering) For any edge u → v in a DAG, finish[u] > finish[v]. Hence decreasing finish time is a valid topological order.

Proof Consider edge u → v when DFS explores u. Either v is white — then DFS visits it now as a descendant of u, so v finishes before u returns, giving finish[v] < finish[u]. Or v is black — already finished, so finish[v] < finish[u] trivially. v cannot be gray in a DAG (that would be a back-edge = cycle). Either way finish[u] > finish[v]. ∎

📊 Complexity

Metric	Value
Time	O(V + E)
Space	O(V) — color array + recursion stack

Depth risk: deep chains can overflow the recursion stack; know the explicit-stack conversion for large inputs.

💻 Reference Implementation (Java)

import java.util.*;

private int[] color;      // 0=white, 1=gray, 2=black
private Deque<Integer> stack;
private boolean hasCycle;

public List<Integer> topoSort(int n, List<Integer>[] adj) {
    color = new int[n];
    stack = new ArrayDeque<>();
    hasCycle = false;
    for (int u = 0; u < n; u++)
        if (color[u] == 0) dfs(u, adj);
    if (hasCycle) return new ArrayList<>();  // no valid order
    List<Integer> order = new ArrayList<>();
    while (!stack.isEmpty()) order.add(stack.pop()); // reversed post-order
    return order;
}

private void dfs(int u, List<Integer>[] adj) {
    color[u] = 1;                       // gray: on the stack
    for (int v : adj[u]) {
        if (color[v] == 1) { hasCycle = true; return; } // back-edge!
        if (color[v] == 0) dfs(v, adj);
    }
    color[u] = 2;                       // black: finished
    stack.push(u);                     // post-order push
}

🎭 Problem Variances — cycle detection & ordering in disguise

Disguise / phrasing	What's really asked	Twist to handle
"Detect deadlock / circular dependency"	Directed cycle detection	3-color DFS; a simple visited set is NOT enough for directed graphs
"Eventual safe nodes / states"	Nodes on or leading to a cycle are unsafe	Color-based: safe = finishes black without touching gray
"Can everything be finished?"	Is the dependency graph a DAG?	Boolean; either Kahn count or DFS coloring
"Find redundant edge (directed)"	Edge whose removal breaks a cycle / restores tree	Union-Find won't work directed; needs DFS/parent reasoning
"Longest path in DAG"	DP over topo order	Topo sort first, then relax forward in that order
"Compile / evaluate in order with cycle guard"	Topo order + reject on cycle	Combine ordering and detection in one pass

Undirected vs directed cycles: undirected → Union-Find or "visited-but-not-parent" DFS. Directed → 3-color DFS or Kahn's count. Interviewers love to check you know the difference.

⚠️ Common Pitfalls

Using a plain visited set for directed cycles: it can't tell "ancestor on stack" from "already done elsewhere." You need the gray state.

Forgetting to reverse: post-order alone is reverse topo order. Push to a stack (or reverse the list).

Marking black too early: set black only after the neighbor loop, or you'll miss back-edges.

🎯 Problems

LC 802 Find Eventual Safe States 3-color DFS; a node is safe iff it never reaches a gray (cycle) node. Med

LC 269 Alien Dictionary Extract order edges from adjacent words, then topo sort; guard the invalid-prefix case. Hard

LC 310 Minimum Height Trees Undirected leaf-peeling — topo-style, but on degree-1 nodes; stop at ≤2 centers. Med

📚 References

CLRS, 3rd ed., §22.3 — DFS, edge classification (tree/back/forward/cross), the white-path theorem.
CLRS, §22.4 — Topological sort via DFS finish times (Theorem 22.11 / Lemma 22.12).
Tarjan, R. E. (1972) — "Depth-first search and linear graph algorithms," SIAM J. Computing 1(2).

← Day 11: Kahn's Day 13: Kruskal's MST →