Cycle Detection · Directed Graph

Can you finish all courses? Only if the prerequisite graph has no cycle. DFS with three colors catches a cycle the instant it revisits a node still on the current path.

Concept

The 3-color trick

White = untouched, Gray = on the current DFS path (in the recursion stack), Black = fully explored and safe.

A directed cycle exists the moment DFS steps onto a gray node, that's a back edge pointing at an ancestor.

Why gray matters

Hitting black is fine, that subtree is already cleared
Hitting gray means you looped back onto your own path
Mark gray on entry, flip to black on exit
No cycle anywhere → a valid topological order exists

Interactive

Trace the DFS path

White (unvisited) Gray (on path) Black (done) Cycle edge

slowfast

Step 0

On path (gray)

Done (black)

At node

–

Cycle?

Implementation

C++

// color: 0 = white, 1 = gray (on path), 2 = black (done)
bool dfs(int u, vector<vector<int>>& adj, vector<int>& color) {
    color[u] = 1;                       // enter: mark gray
    for (int v : adj[u]) {
        if (color[v] == 1) return true;   // back edge → cycle
        if (color[v] == 0 && dfs(v, adj, color)) return true;
    }
    color[u] = 2;                       // exit: mark black
    return false;
}

bool canFinish(int n, vector<vector<int>>& prereq) {
    vector<vector<int>> adj(n);
    for (auto& p : prereq) adj[p[1]].push_back(p[0]);
    vector<int> color(n, 0);
    for (int i = 0; i < n; i++)
        if (color[i] == 0 && dfs(i, adj, color))
            return false;          // cycle → can't finish
    return true;
}

Complexity

Time

O(V + E)

Each vertex is colored once; each edge is examined once during DFS.

Space

O(V + E)

Adjacency list plus the color array and recursion stack.

Detects

back edge

A gray-to-gray edge is a back edge, the signature of a directed cycle.

Notes

Two colors aren't enough for directed graphs. You must distinguish "on the current path" (gray) from "already finished" (black), or you'll false-alarm on shared subtrees.
Kahn's BFS (indegree) is the alternative: if you can't remove all nodes, a cycle remains. Same problem, different lens.
Course Schedule reduces exactly to "is this prerequisite graph a DAG?"
Build edges prereq → course so a valid order flows in dependency direction.
Undirected cycle detection is different, there you track the parent, not colors.