Detect cycle in a directed graph (DSA)

 

problem Statement:(👈click here for GFG)

Given a Directed Graph with V vertices (Numbered from 0 to V-1) and E edges, check whether it contains any cycle or not.

Example 1:

Input:



Output: 1
Explanation: 3 -> 3 is a cycle

Example 2:

Input:


Output: 0
Explanation: no cycle in the graph

Your task:
You dont need to read input or print anything. Your task is to complete the function isCyclic() which takes the integer V denoting the number of vertices and adjacency list as input parameters and returns a boolean value denoting if the given directed graph contains a cycle or not.

Expected Time Complexity: O(V + E)
Expected Auxiliary Space: O(V)

Constraints:
1 ≤ V, E ≤ 10^5

Solution:

class Solution {
  // Function to detect cycle in a directed graph.
  isCyclic(V, adj) {
    // Create arrays to keep track of visited nodes and nodes in the current recursion stack.
    let visited = new Array(V).fill(false);
    let recStack = new Array(V).fill(false);

    // Helper function to check if the graph contains a cycle.
    function isCyclicHelper(node) {
      visited[node] = true;
      recStack[node] = true;

      // Check all adjacent nodes.
      for (let i = 0; i < adj[node].length; i++) {
        let neighbor = adj[node][i];

        // If the neighbor is not visited yet, recursively check if it is part of a cycle.
        if (!visited[neighbor] && isCyclicHelper(neighbor)) {
          return true;
        }

        // If the neighbor is already in the recursion stack, a cycle has been found.
        else if (recStack[neighbor]) {
          return true;
        }
      }

      // Remove the current node from the recursion stack.
      recStack[node] = false;

      return false;
    }

    // Check if the graph contains a cycle.
    for (let i = 0; i < V; i++) {
      if (!visited[i] && isCyclicHelper(i)) {
        return true;
      }
    }

    return false;
  }
}