Given a directed graph with V vertices (0 .. V-1) and directed edges edges (each [u, v] is an edge u → v), return true if it contains a cycle and false otherwise.
Input: V = 3, edges = [[0,1],[1,2],[2,0]] Output: true 0→1→2→0 is a directed cycle.
Input: V = 4, edges = [[0,1],[0,2],[1,3],[2,3]] Output: false A diamond re-reaches 3 via two paths but has no cycle.
- 1 <= V <= 10^5 - 0 <= edges.length <= 10^5 - edges are directed u -> v - no self-loops or duplicate edges
Directed cycles need a different test than undirected ones — the parent trick fails, because a directed graph can revisit a vertex with no cycle (e.g. a diamond a→b→d, a→c→d). Two correct methods:
DFS with a recursion stack. Track three states: unvisited, on the current path, and finished. A cycle exists iff DFS follows an edge to a vertex that's currently on the path — a back edge. (Reaching a finished vertex is fine; that's just a shared descendant.)
Kahn's algorithm. Run the in-degree BFS. If it manages to output all V vertices, the graph is a DAG; if it outputs fewer, the leftover vertices are trapped in a cycle (their in-degrees never reach 0). Both are O(V + E).
“Why doesn't the undirected parent trick work?”
A directed graph can re-reach a vertex via a different path without a cycle.
“Disconnected graph?”
Start DFS/Kahn from every vertex / all in-degree-0 vertices.
I DFS tracking which vertices are on the current recursion path; an edge back to one of them is a cycle.
Or Kahn's: if the topological order can't include all V vertices, a cycle blocked the rest.
Worked example — V = 3, edges [[0,1],[1,2],[2,0]]
DFS 0 -> 1 -> 2 -> edge to 0, which is on the path -> cycle Kahn: no vertex has in-degree 0 -> orders 0 of 3 -> cycle
An edge to a vertex on the current path closes a directed cycle.
On-path vs finished distinguishes real cycles from shared descendants.
If fewer than V vertices are ordered, the rest form a cycle.
| DFS recursion stack | Kahn's algorithm | |
|---|---|---|
| Signal | back edge to an on-path vertex | ordered fewer than V vertices |
| Time | O(V+E) | O(V+E) |
| Also gives | the cycle if tracked | a topological order if acyclic |
Both detect the same directed cycles. Full code is in the Approaches selector below.
Key takeaway
A directed cycle is a back edge to a vertex on the DFS recursion stack; equivalently, Kahn's algorithm fails to order all V vertices. O(V+E).
dfs: if edge to an on-path vertex -> cycle kahn: if ordered count < V -> cycle
