Log inSign up
mediumGeeksforGeeksNot Started

Detect Cycle in Directed Graph

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Graph
Solve on GeeksforGeeks
Lesson

Problem Statement

### Problem Statement

Given a Directed Graph with V vertices numbered from 0 to V - 1 and E directed edges represented by an adjacency list adj, determine whether the graph contains any directed cycle.

A directed cycle exists if there is a path from a vertex u back to itself following directed edges. The graph may be disconnected.

---

### Examples

Example 1: ``text Input: V = 4, E = 4, adj = [[1], [2], [3], [1]] 0 ---> 1 ---> 2 ^ | | v +----- 3 Output: true Explanation: Vertex 1 -> 2 -> 3 -> 1 forms a directed cycle.

Example 2: ``text Input: V = 4, E = 3, adj = [[1], [2], [3], []] 0 ---> 1 ---> 2 ---> 3 Output: false Explanation: The graph is a directed acyclic graph (DAG).

---

### Constraints - 1 <= V <= 10^5 - 0 <= E <= 10^5 - 0 <= adj[i][j] < V - Graph is directed and may contain multiple components.

Constraints:

  • 1 <= V <= 105
  • 0 <= E <= 105
  • 0 <= adj[i][j] < V
  • Graph is directed

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Distinguish back-edges from cross-edges and forward-edges in directed graphs.
  • Implement cycle detection using the inStack / pathVisited DFS backtracking pattern.
  • Implement Kahn's algorithm (BFS in-degrees) for cycle detection.

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Detect if a directed graph contains any directed loop/cycle
  • Deadlock detection or circular dependency resolution (e.g. Course Schedule)
  • Checking if a directed graph is a DAG (Directed Acyclic Graph)

Algorithmic Decision Tree:

  • If directed graph -> Use visited + inStack arrays (or Kahn's BFS).
  • If inStack[neighbor] == true -> Back-edge confirmed, return true.
  • Reset inStack[u] = false upon backtracking.

Connected Patterns:

Course Schedule (Topological Sort)Course Schedule IIFind Eventual Safe States

1. Kahn's Algorithm (BFS In-Degree Topological Sort)

Intuition

In a Directed Acyclic Graph (DAG), at least one vertex must have in-degree 0. Removing in-degree 0 vertices iteratively must consume all V vertices. If a cycle exists, the vertices in the cycle have mutually dependent edges and their in-degrees never reach 0, meaning total processed vertices < V.

Algorithm

  1. Compute in-degrees of all V vertices.
  2. Enqueue all vertices with inDegree[u] == 0 into queue q.
  3. Initialize count = 0.
  4. While queue is not empty:
  5. Pop u from q, count++.
  6. For each neighbor v in adj[u]:
  7. inDegree[v]--.
  8. If inDegree[v] == 0: push v into q.
  9. Return count < V (if fewer than V vertices processed, cycle exists).
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <queue>
4
5class Solution {
6public:
7 bool isCyclic(int V, std::vector<std::vector<int>>& adj) {
8 std::vector<int> inDegree(V, 0);
9 for (int u = 0; u < V; ++u) {
10 for (int v : adj[u]) {
11 inDegree[v]++;
12 }
13 }
14
15 std::queue<int> q;
16 for (int i = 0; i < V; ++i) {
17 if (inDegree[i] == 0) {
18 q.push(i);
19 }
20 }
21
22 int count = 0;
23 while (!q.empty()) {
24 int u = q.front();
25 q.pop();
26 count++;
27
28 for (int v : adj[u]) {
29 inDegree[v]--;
30 if (inDegree[v] == 0) {
31 q.push(v);
32 }
33 }
34 }
35
36 return count < V; // Cycle exists if topological sort incomplete
37 }
38};
39
40int main() {
41 Solution sol;
42 std::vector<std::vector<int>> adj = {{1}, {2}, {3}, {1}};
43 std::cout << "Kahn's Cycle: " << (sol.isCyclic(4, adj) ? "true" : "false") << " (Expected: true)\n";
44 return 0;
45}

Time & Space Complexity

  • Time complexity: O(V + E)
  • Space complexity: O(V)

2. Tri-Color DFS (3-State Array)

Intuition

Combining visited and inStack into a single tri-state array saves memory and simplifies state transitions. Encountering a GRAY node confirms a back-edge to an active ancestor.

Algorithm

  1. Initialize color array of size V to 0 (WHITE).
  2. Define dfs(u):
  3. color[u] = 1 (GRAY = visiting).
  4. For each neighbor v in adj[u]:
  5. If color[v] == 1: return true (back-edge to active ancestor).
  6. If color[v] == 0 and dfs(v): return true.
  7. color[u] = 2 (BLACK = completely processed).
  8. Return false.
  9. Loop i from 0 to V - 1:
  10. If color[i] == 0 and dfs(i): return true.
  11. Return false.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3
4class Solution {
5 bool dfs(int u, const std::vector<std::vector<int>>& adj, std::vector<int>& color) {
6 color[u] = 1; // GRAY = currently visiting
7
8 for (int v : adj[u]) {
9 if (color[v] == 1) return true; // Found active ancestor -> cycle
10 if (color[v] == 0 && dfs(v, adj, color)) return true;
11 }
12
13 color[u] = 2; // BLACK = finished
14 return false;
15 }
16public:
17 bool isCyclic(int V, std::vector<std::vector<int>>& adj) {
18 std::vector<int> color(V, 0); // 0: WHITE, 1: GRAY, 2: BLACK
19
20 for (int i = 0; i < V; ++i) {
21 if (color[i] == 0) {
22 if (dfs(i, adj, color)) return true;
23 }
24 }
25 return false;
26 }
27};
28
29int main() {
30 Solution sol;
31 std::vector<std::vector<int>> adj = {{1}, {2}, {3}, {1}};
32 std::cout << "Tri-Color Cycle: " << (sol.isCyclic(4, adj) ? "true" : "false") << " (Expected: true)\n";
33 return 0;
34}

Time & Space Complexity

  • Time complexity: O(V + E)
  • Space complexity: O(V)

3. Canonical DFS with Visited and PathVisited (Industry Benchmark)

Intuition

The universally taught interview pattern for directed cycles. visited[u] avoids re-traversing subgraphs that have already been proven acyclic. pathVisited[u] tracks the current branch: if an outgoing edge hits a node with pathVisited[v] == true, that edge points to an ancestor, confirming a directed cycle.

Algorithm

  1. Initialize visited and pathVisited boolean arrays of size V to false.
  2. Define dfs(u):
  3. visited[u] = true.
  4. pathVisited[u] = true.
  5. For each neighbor v in adj[u]:
  6. If !visited[v]:
  7. If dfs(v): return true.
  8. Else if pathVisited[v]:
  9. Return true (back-edge detected).
  10. pathVisited[u] = false (backtrack).
  11. Return false.
  12. Loop i from 0 to V - 1:
  13. If !visited[i]:
  14. If dfs(i): return true.
  15. Return false.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3
4class Solution {
5 bool dfs(int u, const std::vector<std::vector<int>>& adj, std::vector<bool>& visited, std::vector<bool>& pathVisited) {
6 visited[u] = true;
7 pathVisited[u] = true;
8
9 for (int v : adj[u]) {
10 if (!visited[v]) {
11 if (dfs(v, adj, visited, pathVisited)) return true;
12 } else if (pathVisited[v]) {
13 return true; // Back-edge implies cycle
14 }
15 }
16
17 pathVisited[u] = false; // Backtrack
18 return false;
19 }
20public:
21 bool isCyclic(int V, std::vector<std::vector<int>>& adj) {
22 std::vector<bool> visited(V, false);
23 std::vector<bool> pathVisited(V, false);
24
25 for (int i = 0; i < V; ++i) {
26 if (!visited[i]) {
27 if (dfs(i, adj, visited, pathVisited)) return true;
28 }
29 }
30 return false;
31 }
32};
33
34int main() {
35 Solution sol;
36 std::vector<std::vector<int>> adj = {{1}, {2}, {3}, {1}};
37 std::cout << "Canonical Cycle: " << (sol.isCyclic(4, adj) ? "true" : "false") << " (Expected: true)\n";
38 return 0;
39}

Time & Space Complexity

  • Time complexity: O(V + E)
  • Space complexity: O(V)

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Kahn's In-Degree BFSO(V + E)O(V)Tracks in-degrees; cycle exists if processed vertices count < V.Queue memory footprint
2.Tri-Color DFSO(V + E)O(V)Single color array with states 0 (unvisited), 1 (visiting), 2 (finished).Call stack depth
3.Canonical DFS with Visited & PathVisitedOptimalO(V + E)O(V)Dual boolean arrays: visited avoids re-work; pathVisited catches back-edges.Call stack depth

Common Pitfalls & Crucial Edge Cases

Pitfall 1:

Treating visited[v] == true as a cycle without checking pathVisited / recursion stack.

Pitfall 2:

Forgetting to backtrack pathVisited[u] = false after visiting neighbors.

Pitfall 3:

Not wrapping DFS in an outer loop over all vertices 0 to V - 1.

Crucial Edge Cases to Validate:

  • Directed graph with multiple disconnected components — Outer loop checks every unvisited vertex from 0 to V - 1, detecting cycles in any disconnected component.
  • Directed Acyclic Graph (DAG) with diamond branches (0->1, 0->2, 1->3, 2->3) — Cross-edge to 3 does not have pathVisited[3] == true; correctly returns false.
  • Self-loop (edge u -> u) — Immediately encounters pathVisited[u] == true on first neighbor check, returns true.

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. Clearly explain the four edge types in directed DFS: Tree edges, Back-edges, Forward edges, and Cross-edges.
  2. Emphasize: 'Only BACK-EDGES form cycles, and a back-edge is characterized by pointing to a vertex currently in pathVisited.'
  3. Mention Kahn's algorithm as an iterative alternative that also produces a topological sort.

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.Why does visited[v] == true NOT necessarily indicate a cycle in a directed graph?

2.What must be done to pathVisited[u] when the DFS finishes exploring all neighbors of vertex u?

3.How does Kahn's algorithm determine that a directed graph contains a cycle?

Back to DSA Sheet