Detect Cycle in a Directed Graph Easy 0 attempts
GeeksforGeeks ↗

Detect Cycle in a Directed Graph

Easy GraphBFSDFS GeeksforGeeks

You're given a directed graph with V vertices and an adjacency list adj, where adj[u] lists the destinations of edges leaving u. Determine whether following the edges can ever lead back to a vertex already visited — in other words, whether the graph contains a cycle.

Input Format
Implement hasCycle(V, adj). Inputs below show JavaScript function arguments; there is no stdin parsing.
Output Format
Return the result described in the statement.

Sample Input and Output

Example 1 · Run Sample

Input
V = 4
adj = [[1],[2],[3],[1]]
Output
true

Example 2

Input
V = 3
adj = [[1],[2],[]]
Output
false
Constraints
  • 1 <= V <= 10^4
  • 0 <= E <= 10^4
Test Cases (2)
Case 1
Args: [4,[[1],[2],[3],[1]]] Expected: true
Case 2
Args: [3,[[1],[2],[]]] Expected: false
Topics
GraphBFSDFS

Iterative DFS with Active Frames

Track unvisited, active, and finished vertices. Each stack frame stores the next edge to examine. An edge to an active vertex closes a directed cycle.

javascript
function hasCycle(V, adj) {
  const color=Array(V).fill(0);
  for(let start=0;start<V;start++)if(color[start]===0){
    const stack=[[start,0]];color[start]=1;
    while(stack.length){const frame=stack[stack.length-1],u=frame[0];
      if(frame[1]===adj[u].length){color[u]=2;stack.pop();continue;}
      const v=adj[u][frame[1]++];if(color[v]===1)return true;if(color[v]===0){color[v]=1;stack.push([v,0]);}
    }
  }
  return false;
}

Time: O(V + E) | Space: O(V)

Saved in this browser only. Private to you.

JavaScript