The challenge
Determine whether a directed graph contains a cycle, using DFS states to distinguish an active ancestor from a vertex whose search has already finished.
This three-state test is for directed graphs. In undirected graphs, skip the parent edge or use DSU.
Example
The DAG has no cycle. Add D → B and the active path B → C → D returns to B.
Use the walkthrough below to inspect the input and each state change.
See Directed cycles, step by step
Follow the edges. Watch the state change.
Directed · 6 vertices · 6 edgesA = 0, B = 1, …
CurrentVisited / acceptedUnvisited
| A | B | C | D | E | F |
|---|---|---|---|---|---|
| unseen | unseen | unseen | unseen | unseen | unseen |
Step 01 / 14
Track three states per vertex.
Unseen vertices have not been entered; active vertices are on the recursion path; done vertices have finished.
state = [0] * VActive DFS path · top last
Empty
View input edges
A → B · A → F · B → C · F → C · C → D · D → E
Put it into code
An edge to an active vertex closes a directed cycle; an edge to a finished vertex does not.
Vertices are numbered 0 to V − 1. C++ uses C++17 or later.
def has_directed_cycle(adj):
state = [0] * len(adj) # 0: unseen, 1: active, 2: done
def visit(u):
state[u] = 1
for v in adj[u]:
if state[v] == 1:
return True # Back edge into the active path.
if state[v] == 0 and visit(v):
return True
state[u] = 2
return False
for u in range(len(adj)):
if state[u] == 0 and visit(u):
return True
return False#include <functional>
#include <vector>
bool has_directed_cycle(const std::vector<std::vector<int>>& adj) {
int n = static_cast<int>(adj.size());
std::vector<int> state(n, 0);
std::function<bool(int)> visit = [&](int u) {
state[u] = 1;
for (int v : adj[u]) {
if (state[v] == 1) return true;
if (state[v] == 0 && visit(v)) return true;
}
state[u] = 2;
return false;
};
for (int u = 0; u < n; ++u)
if (state[u] == 0 && visit(u)) return true;
return false;
}