Detect Cycle in Directed Graph
Description
Given a directed graph with V vertices (numbered 0 to V-1) and E edges represented as an adjacency list, determine whether the graph contains a cycle or not.
A cycle in a directed graph is a path that starts at some vertex, follows directed edges, and eventually returns to the same starting vertex. In other words, there exists a sequence of vertices v₀ → v₁ → v₂ → ... → vₖ → v₀ where each arrow represents a directed edge.
Return true if the graph contains at least one cycle, and false otherwise.
Note that this problem deals specifically with directed graphs. Cycle detection in directed graphs is fundamentally different from undirected graphs because the direction of edges matters — having edges A→B and B→C does not necessarily mean C can reach A.
Examples
Example 1
Input: V = 5, adj = [[1], [2], [0], [4], []]
Output: true
Explanation: The graph contains the cycle 0 → 1 → 2 → 0. Starting at vertex 0, we follow edge 0→1, then 1→2, then 2→0 which brings us back to the starting vertex. Vertices 3 and 4 are not part of the cycle (3→4 is a one-way path with no return), but the presence of even one cycle makes the entire answer true.
Example 2
Input: V = 4, adj = [[1, 2], [2], [3], []]
Output: false
Explanation: The graph has edges 0→1, 0→2, 1→2, and 2→3. Although there are multiple paths (e.g., 0→1→2→3 and 0→2→3), none of them form a cycle. Vertex 3 is a terminal vertex with no outgoing edges, so any path reaching vertex 3 cannot continue. This graph is a Directed Acyclic Graph (DAG).
Example 3
Input: V = 3, adj = [[1], [2], [0]]
Output: true
Explanation: Every vertex participates in the cycle 0 → 1 → 2 → 0. This is a complete directed cycle where each vertex has exactly one incoming and one outgoing edge. No matter which vertex you start from, following the edges will eventually bring you back.
Constraints
- 1 ≤ V ≤ 10^5
- 0 ≤ E ≤ 10^5
- 0 ≤ adj[i][j] < V
- The graph is directed
- The graph may contain self-loops
- The graph may be disconnected
Editorial
Brute Force
Intuition
The most straightforward way to detect a cycle is to ask a direct question: for each vertex in the graph, can we start at that vertex, follow directed edges, and eventually return to it?
Imagine you are in a city with one-way streets. To check if any circular route exists, you could stand at each intersection and try to drive back to where you started. If from any intersection you can complete a round trip, there is a cycle.
For each vertex u, we run a complete BFS or DFS starting from u and check if any path leads back to u. If we can reach u from itself by following edges, then u is part of a cycle.
Step-by-Step Explanation
Let's trace through with V = 5, adj = [[1], [2], [0], [4], []]:
Edges: 0→1, 1→2, 2→0, 3→4
Step 1: Check vertex 0. Start a BFS/DFS from vertex 0.
- From 0, we can reach 1 (via edge 0→1).
- From 1, we can reach 2 (via edge 1→2).
- From 2, we can reach 0 (via edge 2→0).
- We reached vertex 0 again! Vertex 0 can reach itself.
Step 2: Cycle detected at vertex 0! The path 0 → 1 → 2 → 0 forms a directed cycle.
Step 3: Return true immediately. No need to check remaining vertices.
In the worst case (no cycle), we would need to check all V vertices:
Step 4 (hypothetical — no cycle case): For vertex 0, BFS explores all reachable nodes. If 0 is not among them, no cycle through 0.
Step 5 (hypothetical): Repeat for vertex 1, 2, ..., V-1. Each BFS traversal takes O(V + E) time.
Step 6 (hypothetical): After checking all V vertices with no self-reachability found, return false. Total: V separate BFS traversals.
Algorithm
- For each vertex u from 0 to V-1:
a. Run a BFS (or DFS) starting from u
b. During the traversal, if we encounter u again, return true (cycle found) - If no vertex can reach itself after checking all vertices, return false
Code
#include <vector>
#include <queue>
using namespace std;
class Solution {
public:
bool isCyclic(vector<vector<int>>& adj) {
int V = adj.size();
for (int u = 0; u < V; u++) {
// BFS from u to check if u is reachable from itself
vector<bool> visited(V, false);
queue<int> q;
for (int v : adj[u]) {
q.push(v);
visited[v] = true;
}
while (!q.empty()) {
int curr = q.front();
q.pop();
if (curr == u) return true; // Reached back to u
for (int next : adj[curr]) {
if (!visited[next]) {
visited[next] = true;
q.push(next);
}
}
}
}
return false;
}
};from collections import deque
class Solution:
def isCyclic(self, adj):
V = len(adj)
for u in range(V):
# BFS from u to check if u is reachable from itself
visited = [False] * V
queue = deque()
for v in adj[u]:
queue.append(v)
visited[v] = True
while queue:
curr = queue.popleft()
if curr == u:
return True # Reached back to u
for nxt in adj[curr]:
if not visited[nxt]:
visited[nxt] = True
queue.append(nxt)
return Falseimport java.util.*;
class Solution {
public boolean isCyclic(List<List<Integer>> adj) {
int V = adj.size();
for (int u = 0; u < V; u++) {
// BFS from u to check if u is reachable from itself
boolean[] visited = new boolean[V];
Queue<Integer> queue = new LinkedList<>();
for (int v : adj.get(u)) {
queue.offer(v);
visited[v] = true;
}
while (!queue.isEmpty()) {
int curr = queue.poll();
if (curr == u) return true; // Reached back to u
for (int next : adj.get(curr)) {
if (!visited[next]) {
visited[next] = true;
queue.offer(next);
}
}
}
}
return false;
}
}Complexity Analysis
Time Complexity: O(V × (V + E))
For each of the V vertices, we run a complete BFS that visits up to V vertices and examines up to E edges. In the worst case (no cycle found until all vertices checked), we perform V separate BFS traversals, each costing O(V + E). Total: O(V × (V + E)).
Space Complexity: O(V)
Each BFS uses a visited array of size V and a queue that can hold at most V elements. Since we reuse these structures for each vertex, the space at any given time is O(V).
Why This Approach Is Not Efficient
The brute force runs V independent BFS traversals, each costing O(V + E). With V up to 10^5 and E up to 10^5, the total operations can reach 10^5 × (10^5 + 10^5) = 2 × 10^10, which far exceeds typical time limits.
The fundamental problem is redundancy: we are re-exploring the same portions of the graph multiple times. When we check vertex 0, we discover that 0 can reach 1 and 2. When we later check vertex 1, we explore much of the same subgraph again. We discard all the information gathered from each BFS and start fresh for the next vertex.
The key insight: instead of asking "can vertex u reach itself?" for each vertex independently, we can detect cycles in a single traversal by tracking which vertices are on the current exploration path. If during a DFS from any vertex, we encounter a vertex that is already on the current path, we have found a cycle — a single pass suffices.
Better Approach - DFS with Recursion Stack
Intuition
Instead of checking each vertex independently, we can detect cycles using a single DFS traversal with an additional tracking mechanism called the recursion stack.
Think of the DFS traversal as exploring a cave system with string. You tie string to your starting position and unspool it as you go deeper. If at any point you encounter your own string (not someone else's old, abandoned string), you know you have circled back — you found a loop.
The algorithm maintains two boolean arrays:
- visited[] — tracks whether a vertex has ever been explored (like old string from previous explorations)
- recStack[] — tracks whether a vertex is on the current active DFS path (like fresh string from your current exploration)
The critical distinction: visited[v] = true only means some earlier DFS call already processed vertex v. But recStack[v] = true means vertex v is an ancestor in the current DFS path — reaching it means we followed a sequence of edges that loops back to an ancestor, forming a directed cycle.
When we finish exploring all neighbors of a vertex (about to backtrack), we remove it from the recursion stack. This correctly handles cases where two separate DFS trees share some reachable vertices — shared vertices are "visited" but not on the current path.
Step-by-Step Explanation
Let's trace through with V = 5, adj = [[1], [2], [0], [4], []]:
Edges: 0→1, 1→2, 2→0, 3→4
Step 1: Initialize visited = [F, F, F, F, F] and recStack = [F, F, F, F, F]. Start iterating from vertex 0.
Step 2: Vertex 0 is unvisited. Call DFS(0). Set visited[0] = true, recStack[0] = true. The current active DFS path is: {0}.
Step 3: Vertex 0 has neighbor 1. Node 1 is unvisited. Call DFS(1). Set visited[1] = true, recStack[1] = true. Active path: {0, 1}.
Step 4: Vertex 1 has neighbor 2. Node 2 is unvisited. Call DFS(2). Set visited[2] = true, recStack[2] = true. Active path: {0, 1, 2}.
Step 5: Vertex 2 has neighbor 0. Check: visited[0] = true. Is node 0 already visited?
Step 6: Check recStack[0] — it is true! Node 0 is on the current active DFS path. This means we followed the path 0 → 1 → 2 and arrived back at 0. This is a back edge indicating a directed cycle.
Step 7: Cycle confirmed: 0 → 1 → 2 → 0. Return true immediately without exploring the rest of the graph.
Note: Vertices 3 and 4 are never even reached because we found the cycle early. In a no-cycle case, DFS would explore all vertices and never find a recStack conflict.
DFS with Recursion Stack — Detecting Back Edges — Watch how DFS maintains a recursion stack to track the current path. When we encounter a vertex already on the current path (a back edge), a cycle is confirmed.
Algorithm
- Initialize two boolean arrays: visited[V] and recStack[V], both set to false
- For each vertex i from 0 to V-1:
- If vertex i is not visited, call DFS(i)
- If DFS(i) returns true, return true (cycle found)
- DFS(u):
a. Set visited[u] = true and recStack[u] = true
b. For each neighbor v of u:- If recStack[v] is true, return true (back edge = cycle)
- If visited[v] is false, recursively call DFS(v). If it returns true, return true
c. Set recStack[u] = false (backtrack: remove u from current path)
d. Return false (no cycle found through u)
- If no DFS call detects a cycle, return false
Code
#include <vector>
using namespace std;
class Solution {
public:
bool dfs(int u, vector<vector<int>>& adj, vector<bool>& visited, vector<bool>& recStack) {
visited[u] = true;
recStack[u] = true;
for (int v : adj[u]) {
// Back edge: v is on the current DFS path
if (recStack[v]) return true;
// Unvisited vertex: explore it
if (!visited[v] && dfs(v, adj, visited, recStack)) {
return true;
}
}
// Backtrack: remove u from current path
recStack[u] = false;
return false;
}
bool isCyclic(vector<vector<int>>& adj) {
int V = adj.size();
vector<bool> visited(V, false);
vector<bool> recStack(V, false);
for (int i = 0; i < V; i++) {
if (!visited[i]) {
if (dfs(i, adj, visited, recStack)) {
return true;
}
}
}
return false;
}
};class Solution:
def isCyclic(self, adj):
V = len(adj)
visited = [False] * V
rec_stack = [False] * V
def dfs(u):
visited[u] = True
rec_stack[u] = True
for v in adj[u]:
# Back edge: v is on the current DFS path
if rec_stack[v]:
return True
# Unvisited vertex: explore it
if not visited[v] and dfs(v):
return True
# Backtrack: remove u from current path
rec_stack[u] = False
return False
for i in range(V):
if not visited[i]:
if dfs(i):
return True
return Falseimport java.util.*;
class Solution {
private boolean dfs(int u, List<List<Integer>> adj, boolean[] visited, boolean[] recStack) {
visited[u] = true;
recStack[u] = true;
for (int v : adj.get(u)) {
// Back edge: v is on the current DFS path
if (recStack[v]) return true;
// Unvisited vertex: explore it
if (!visited[v] && dfs(v, adj, visited, recStack)) {
return true;
}
}
// Backtrack: remove u from current path
recStack[u] = false;
return false;
}
public boolean isCyclic(List<List<Integer>> adj) {
int V = adj.size();
boolean[] visited = new boolean[V];
boolean[] recStack = new boolean[V];
for (int i = 0; i < V; i++) {
if (!visited[i]) {
if (dfs(i, adj, visited, recStack)) {
return true;
}
}
}
return false;
}
}Complexity Analysis
Time Complexity: O(V + E)
Each vertex is visited exactly once (the visited check prevents re-processing). For each vertex, we iterate over all its outgoing edges. Across all vertices, every edge is examined once. The recursion stack marking and unmarking are O(1) per vertex. Total: O(V + E).
Space Complexity: O(V)
The visited and recStack arrays each take O(V) space. The recursion call stack can grow up to O(V) frames deep in the worst case (a linear chain of V vertices). Total auxiliary space: O(V).
Why This Approach Is Not Efficient
While the DFS with recursion stack achieves optimal O(V + E) time complexity, it has practical drawbacks:
1. Recursion Stack Overflow Risk: The algorithm relies on recursive DFS. For graphs with long directed chains (e.g., 0→1→2→...→99999), the recursion depth can reach V = 10^5 frames. Most programming environments have default stack sizes of 1-8 MB, and each stack frame consumes memory for local variables, return addresses, and function parameters. Deep recursion can crash with a stack overflow error.
2. Two Separate Boolean Arrays: The algorithm requires maintaining both visited[] and recStack[] arrays separately, which adds complexity to the implementation. Managing when to set and unset the recStack flags (especially the backtracking step) is a common source of bugs.
3. Not Naturally Iterative: Converting the recursive DFS to an iterative version while correctly maintaining the recursion stack semantics is non-trivial. The backtracking step (recStack[u] = false) is hard to replicate cleanly with an explicit stack.
Key insight for improvement: We can detect cycles without recursion by leveraging a completely different strategy: attempt a topological sort using Kahn's Algorithm (BFS). If the graph has a cycle, topological sorting is impossible — some vertices will never have their in-degree reduced to 0. By counting how many vertices get processed, we can determine if a cycle exists, all without any recursion.
Optimal Approach - Kahn's Algorithm (BFS Indegree)
Intuition
Kahn's Algorithm for topological sorting works only on Directed Acyclic Graphs (DAGs). This limitation is actually a powerful tool: if we attempt Kahn's Algorithm and it fails to process all vertices, the graph must contain a cycle.
Here is the key insight: In Kahn's Algorithm, a vertex enters the processing queue only when its in-degree becomes 0 — meaning all edges pointing to it have been "removed" by processing its predecessors. In a cycle like A→B→C→A, none of these three vertices can ever reach in-degree 0 because each one depends on at least one other vertex in the cycle. They form a deadlock: A waits for C, C waits for B, and B waits for A.
Imagine a group of people sitting in a circle, each person waiting for the person on their left to stand up first before they will stand. No one can ever stand because everyone is waiting. Similarly, in a cycle, no vertex can ever be processed.
So the algorithm is simple: run Kahn's Algorithm and count how many vertices get processed. If the count equals V, the graph is a DAG (no cycle). If the count is less than V, some vertices were stuck in a deadlock — those vertices are part of one or more cycles.
Step-by-Step Explanation
Let's trace through with V = 5, adj = [[1], [2], [0], [4], []]:
Edges: 0→1, 1→2, 2→0, 3→4
Step 1: Compute in-degree for each vertex:
- Vertex 0: 1 incoming edge (from vertex 2) → indegree = 1
- Vertex 1: 1 incoming edge (from vertex 0) → indegree = 1
- Vertex 2: 1 incoming edge (from vertex 1) → indegree = 1
- Vertex 3: 0 incoming edges → indegree = 0
- Vertex 4: 1 incoming edge (from vertex 3) → indegree = 1
Step 2: Find all vertices with indegree 0: only vertex 3. Enqueue vertex 3. Queue: [3]. Processed count: 0.
Step 3: Dequeue vertex 3. Increment processed count to 1. Process edge 3→4: decrease indegree of vertex 4 from 1 to 0. Vertex 4's indegree is now 0 — enqueue vertex 4. Queue: [4].
Step 4: Dequeue vertex 4. Increment processed count to 2. Vertex 4 has no outgoing edges. Queue is empty.
Step 5: Queue is empty. Processed count = 2, but V = 5. Since 2 < 5, not all vertices could be processed.
Step 6: The 3 unprocessed vertices (0, 1, 2) all have indegree > 0 that never reached 0. They are stuck in the cycle 0→1→2→0 — each depends on another in the cycle, creating a deadlock.
Step 7: Since processed count (2) ≠ V (5), the graph contains a cycle. Return true.
Kahn's Algorithm — Cycle Detection via Failed Topological Sort — Watch how Kahn's algorithm processes vertices with no dependencies. Vertices trapped in a cycle can never reach in-degree 0, revealing the cycle when not all vertices are processed.
Algorithm
- Create an array
indegreeof size V, initialized to 0 - For each vertex u, for each neighbor v of u: increment indegree[v]
- Create an empty queue. For each vertex i: if indegree[i] == 0, enqueue i
- Initialize processed_count = 0
- While the queue is not empty:
a. Dequeue vertex u
b. Increment processed_count
c. For each neighbor v of u:- Decrease indegree[v] by 1
- If indegree[v] becomes 0, enqueue v
- If processed_count == V, return false (no cycle — all vertices were topologically sorted)
- If processed_count < V, return true (cycle exists — some vertices could never be processed)
Code
#include <vector>
#include <queue>
using namespace std;
class Solution {
public:
bool isCyclic(vector<vector<int>>& adj) {
int V = adj.size();
vector<int> indegree(V, 0);
// Compute in-degrees
for (int u = 0; u < V; u++) {
for (int v : adj[u]) {
indegree[v]++;
}
}
// Enqueue all vertices with in-degree 0
queue<int> q;
for (int i = 0; i < V; i++) {
if (indegree[i] == 0) {
q.push(i);
}
}
// BFS — attempt topological sort
int processedCount = 0;
while (!q.empty()) {
int u = q.front();
q.pop();
processedCount++;
for (int v : adj[u]) {
indegree[v]--;
if (indegree[v] == 0) {
q.push(v);
}
}
}
// If not all vertices processed, cycle exists
return processedCount != V;
}
};from collections import deque
class Solution:
def isCyclic(self, adj):
V = len(adj)
indegree = [0] * V
# Compute in-degrees
for u in range(V):
for v in adj[u]:
indegree[v] += 1
# Enqueue all vertices with in-degree 0
queue = deque()
for i in range(V):
if indegree[i] == 0:
queue.append(i)
# BFS — attempt topological sort
processed_count = 0
while queue:
u = queue.popleft()
processed_count += 1
for v in adj[u]:
indegree[v] -= 1
if indegree[v] == 0:
queue.append(v)
# If not all vertices processed, cycle exists
return processed_count != Vimport java.util.*;
class Solution {
public boolean isCyclic(List<List<Integer>> adj) {
int V = adj.size();
int[] indegree = new int[V];
// Compute in-degrees
for (int u = 0; u < V; u++) {
for (int v : adj.get(u)) {
indegree[v]++;
}
}
// Enqueue all vertices with in-degree 0
Queue<Integer> queue = new LinkedList<>();
for (int i = 0; i < V; i++) {
if (indegree[i] == 0) {
queue.offer(i);
}
}
// BFS — attempt topological sort
int processedCount = 0;
while (!queue.isEmpty()) {
int u = queue.poll();
processedCount++;
for (int v : adj.get(u)) {
indegree[v]--;
if (indegree[v] == 0) {
queue.offer(v);
}
}
}
// If not all vertices processed, cycle exists
return processedCount != V;
}
}Complexity Analysis
Time Complexity: O(V + E)
Computing in-degrees iterates over all V vertices and E edges: O(V + E). Finding zero-indegree vertices scans all V vertices: O(V). The BFS loop processes at most V vertices, and across all iterations examines each edge at most once: O(V + E). Total: O(V + E).
Space Complexity: O(V)
The indegree array stores V integers. The queue holds at most V vertices. Total auxiliary space: O(V). Critically, this approach is fully iterative — it uses no recursion, so there is zero risk of stack overflow regardless of graph structure or depth. This makes it more robust for large inputs (V up to 10^5) compared to the recursive DFS approach.