Detect Cycle in Directed Graph (DFS)
Detect Cycle in a Directed Graph is a GFG problem (Medium). You are given a directed graph with V vertices numbered 0 … V-1 and a list edges, where edges[i] = [u, v] is an edge from u to v. Return true if the graph contains at least one cycle, and false otherwise.
- A cycle is a path that follows edge directions and returns to the vertex it started from.
- The graph may be disconnected, so a cycle can hide in any part of it.
- A self-loop
u → uis a cycle.
With up to 10⁵ vertices and edges, the check has to be linear, O(V + E).
- 1 <= V <= 10⁵
- 0 <= E <= 10⁵
Intuition
In a directed graph, a cycle exists exactly when a depth-first search finds a back edge: an edge from the current vertex to a vertex that is still on the current DFS path (an ancestor in the recursion). Following that edge leads back to where the path already is, so the path closes into a loop.
A plain visited set cannot tell a back edge apart from a harmless edge into a part of the graph that was already fully explored. So each vertex gets one of three states:
- 0, unvisited: not reached yet;
- 1, on the path: DFS has entered it and not yet left (it is on the recursion stack);
- 2, finished: every vertex reachable from it has been explored, and no cycle was found through it.
An edge to a state-1 vertex is a cycle. An edge to a state-2 vertex is safe and can be skipped: everything behind it is already known to be cycle-free.
Any task that asks you to find a cycle in a directed graph, or just to say whether one exists, fits here. It appears as course prerequisites (Course Schedule, LeetCode 207), build or task dependencies, deadlock detection and "can these be ordered?" questions. DFS with three states answers it; Kahn's algorithm (BFS on in-degrees) is the other standard method and also produces a topological order.
Approach
Before reading on: run DFS with only a visited set on the second example (0→1, 0→2, 1→3, 2→3). What happens when the search reaches 3 a second time from 2? What extra information would tell you that 3 is not an ancestor of 2?
Build the adjacency list
For each [u, v], append v to adj[u]. Only one direction: the graph is directed. A directed edge u → v can be walked only from u.
Mark a vertex as on the path when DFS enters it
Set state[u] = 1 before exploring its edges. A plain visited flag could not tell an edge back into the current path from an edge into an already finished part of the graph, which is why three states are needed.
Classify each outgoing edge
state[v] == 1: back edge, returntrue.state[v] == 0: recurse intov; if that finds a cycle, returntrue.state[v] == 2: already finished and cycle-free, skip it.
Only an edge to a vertex still on the current path can close a loop.
Mark the vertex finished when DFS leaves it
After all its edges, set state[u] = 2. It is no longer on the path, so later edges into it are not cycles.
Start from every unvisited vertex
Launch DFS from each vertex still in state 0. If none finds a back edge, the graph is acyclic. The graph may be disconnected, and a cycle can sit in a part the first DFS never reaches.
Detect Cycle in Directed Graph (DFS) solution in Python | C++ | Java
true all the way up; nothing else needs exploring.Common pitfalls
Using one visited set, as for undirected graphs
if v in visited:
return Trueif state[v] == 1: # on the current path
return TrueIn the second example DFS reaches 3 through 1, then again through 2. With only visited, the second arrival looks like a cycle and the answer is wrongly true. Only an edge back to a vertex still on the path closes a loop.
Starting DFS only from vertex 0
return dfs(0)
return any(state[u] == 0 and dfs(u) for u in range(V))
The graph may be disconnected, or vertex 0 may simply not reach the cycle. With edges [[1, 2], [2, 1]] and V = 3, DFS from 0 finds nothing and returns false.
Edge cases
When DFS enters u, state[u] is 1, so the edge u → u is a back edge and the answer is true at once.
A path of 10⁵ vertices means 10⁵ nested calls, beyond Python's default limit of 1,000. Raise it with sys.setrecursionlimit, or use Kahn's algorithm, which needs no recursion.
Complexity
Cycle detection: DFS vs BFS, directed vs undirected
The right test depends on whether edges have a direction.
| Graph | Method | A cycle is… |
|---|---|---|
| Directed | DFS with 3 states (this page) | an edge to a vertex still on the path (state 1) |
| Directed | Kahn's algorithm (BFS on in-degrees) | fewer than V vertices ever reach in-degree 0 |
| Undirected | DFS with a parent | an edge to a visited vertex that is not the parent |
| Undirected | Union-Find | an edge whose two ends are already in the same set |
Detect Cycle in Directed Graph (DFS) FAQ
How do you detect cycle in directed graph using DFS?
- States: 0 = unvisited, 1 = on the current DFS path, 2 = finished.
- Enter u: set
state[u] = 1. - Each edge u → v: if
state[v] == 1, a cycle exists (back edge); if 0, recurse; if 2, skip. - Leave u: set
state[u] = 2. - Outer loop: start DFS from every unvisited vertex.
- Complexity: O(V + E) time and space.
What is a back edge?
An edge into a vertex still on the recursion stack (state 1). DFS sorts every other edge too:
- Tree edge: into an unvisited vertex (state 0); DFS recurses along it.
- Forward or cross edge: into a finished vertex (state 2); it cannot close a loop.
- Back edge: into state 1; it closes a loop.
Only the last kind means a cycle, which is why state 2 is skipped.