Cycle Detection in a Directed Graph
The obvious approach — flag nodes as visited and cry foul when you meet one again — is wrong, and wrong in a way that passes most test cases. A node can be reachable by two separate paths without any cycle existing. The fix is to distinguish between nodes you are currently inside and nodes you have already finished.
This isn't a canned animation. DryRun compiles and executes the code below, then draws every step from the real trace — the same values your machine would produce.
The code
vector<vector<int> > adj;
vector<int> state;
bool hasCycle(int u) {
state[u] = 1;
for (int i = 0; i < (int)adj[u].size(); i++) {
int v = adj[u][i];
if (state[v] == 1) return true;
if (state[v] == 0 && hasCycle(v)) return true;
}
state[u] = 2;
return false;
}
int main() {
int n = 4;
adj.assign(n, vector<int>());
state.assign(n, 0);
adj[0].push_back(1); adj[0].push_back(2);
adj[1].push_back(3); adj[2].push_back(3);
adj[3].push_back(1);
bool found = false;
for (int i = 0; i < n; i++) {
if (state[i] == 0 && hasCycle(i)) found = true;
}
cout << found << endl;
return 0;
}State 0 is unvisited, 1 is on the current DFS path, and 2 is fully explored — the diamond 0 to 1 and 2 to 3 would fool a single visited flag, while the 3 to 1 edge is the real cycle.
How it works, step by step
Three states, not two
Unvisited means never seen. State 1 means the DFS entered this node and has not returned yet, so it is on the current path. State 2 means the node and everything below it is finished. Only state 1 indicates a cycle.
A back edge is the definition of a cycle
Reaching a node that is still in state 1 means you have found an edge pointing back to an ancestor on the current path — which, combined with the path itself, forms a directed cycle. Nothing else in a DFS can create one.
State 2 nodes are safe to re-encounter
Finishing a node means its entire reachable subgraph has been explored with no cycle found. Meeting it again from a different branch tells you nothing new, so the DFS skips it. This is exactly the case a single visited flag gets wrong.
The mark flips back on exit
Setting state[u] = 2 after the loop is what removes u from the current path. Forget it and every previously explored node stays marked as on-path, so the next branch that touches it reports a phantom cycle.
Every component needs a start
The loop in main launches a DFS from every still-unvisited node, because a cycle can live in a component unreachable from node 0. Nodes finished by an earlier DFS are skipped by the state check, so the total work is still linear.
Complexity
One DFS over the whole graph, with each node entered once and each edge examined once; the space is the state array plus a recursion stack that can reach V frames on a long path.
Common bugs
Using one boolean visited flag
On the diamond 0 to 1, 0 to 2, 1 to 3, 2 to 3, the second path reaches an already-visited node 3 and a boolean check reports a cycle that does not exist. The graph is a perfectly valid DAG. Cross edges to finished nodes are normal; only edges to in-progress nodes matter.
Forgetting to set state to 2 on the way out
If the node stays at 1 after its DFS completes, it looks like it is still on the path forever. Every later branch that touches it reports a cycle, so the function returns true on almost any graph. Stepping through and watching the state array after each return exposes this immediately.
Applying the directed algorithm to an undirected graph
In an undirected graph, every edge is traversable both ways, so u to v and immediately v to u looks like a back edge and every single edge reports a cycle. Undirected cycle detection must skip the edge you arrived on by tracking the parent node.
Starting from only one node
A single call to hasCycle(0) misses cycles in components that node 0 cannot reach. The loop over all vertices is not optional, and its absence produces false negatives on exactly the graphs where a cycle matters most.
Each of these is easier to see than to describe — step through it and watch the values change. Run it in DryRun.
Frequently asked
How do you detect a cycle in a directed graph?
Run a depth-first search that tracks three states per node: unvisited, currently on the DFS path, and fully finished. If you ever follow an edge to a node that is currently on the path, you have found a back edge and therefore a cycle. Finishing a node moves it out of the on-path state so it stops triggering false positives.
Why isn't a visited flag enough to detect a cycle?
Because visited conflates two different situations: a node you are still inside, and a node you have already finished. Reaching a finished node just means it was reachable by more than one path, which is completely normal in an acyclic graph. Only reaching a node that is still on the current recursion path proves a cycle exists.
How is cycle detection different in an undirected graph?
In an undirected graph every edge can be walked both ways, so the edge you arrived on always leads back to a visited node. You detect a cycle by tracking the parent and reporting only when you reach a visited node that is not the parent. The three-colour method is for directed graphs specifically.
What is a back edge?
An edge from a node to one of its ancestors in the current depth-first search tree — that is, to a node whose DFS call has started but not yet returned. Combined with the tree path from that ancestor down to the current node, a back edge closes a directed cycle. A graph is acyclic exactly when a DFS finds no back edges.