Detect cycle in Directed Graph with code in c++

 Detect cycle in a directed graph

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 ≤ 105

solution :

  To detect cycle in directed graph , we uses two Boolean array . first which take record of stacks of recursive function  and second which take record of how much of vertex are visited till now.

it basically uses the concept of DFS alogithm and backtracking also.

The code is here :

class Solution {

  public:

    // Function to detect cycle in a directed graph.

    bool dfs(vector<bool>&visited , vector<bool>&visiteddfs , vector<int>adj[]  , int i)

    {

        visited[i] = true;

        visiteddfs[i] = true;

        vector<int>x = adj[i];

        for(int k = 0 ; k < x.size() ; k++)

        {

            if(!visited[x[k]])

            {

                if(dfs(visited, visiteddfs , adj , x[k]))

                    return true;

            }

            else

            {

                if(visiteddfs[x[k]])

                 return true;

            }

               

        }

        visiteddfs[i] = false;

        return false;

    }

    bool isCyclic(int V, vector<int> adj[]) {

        

        vector<bool>visited(V ,false);

        vector<bool>visiteddfs(V , false);

        for(int i = 0 ; i < V ; i++)

        {     

            if(!visited[i])

              { 

                  if(dfs(visited, visiteddfs , adj , i))

                    return true;

                     

              }

            

        }

        return false;

    }

};

References : https://practice.geeksforgeeks.org/problems/detect-cycle-in-a-directed-graph/1