Graph/directedgraphcycle.cpp at main · aerraj/Graph · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
//{ Driver Code Starts
#include <bits/stdc++.h>
using namespace std;

// } Driver Code Ends
class Solution {
  public:
  bool dfs(int node, vector<int> adj[],int vis[],int pathVis[])
  {
      vis[node]=1;
      pathVis[node]=1;
      for(auto it:adj[node])
      {
          if(!vis[it])
          {
              if(dfs(it,adj,vis,pathVis)==true)
              return true;

          }
          else if(pathVis[it]==1)
          {
              return true;
          }
      }
      pathVis[node]=0;
      return false;
  }
    // Function to detect cycle in a directed graph.
    bool isCyclic(int V, vector<int> adj[]) {
        // code here
        int vis[V]={0};
        int pathVis[V]={0};

        for(int i=0;i<V;i++)
        {
            if(vis[i]==0)
            {
                if(dfs(i,adj,vis,pathVis)==true)
                return true;
            }
        }
        return false;
    }
};
class Solution2
{
public:
    bool dfs(int node, vector<int> adj[], int vis[])
    {
        vis[node] = 2;
        for (auto it : adj[node])
        {
            if (!vis[it])
            {
                if (dfs(it, adj, vis) == true)
                return true;
            }
            else if (vis[it] == 2)
            {
                return true;
            }
        }
        vis[node] = 1;
        return false;
    }
    // Function to detect cycle in a directed graph.
    bool isCyclic(int V, vector<int> adj[])
    {
        // code here
        int vis[V] = {0};

        for (int i = 0; i < V; i++)
        {
            if (vis[i] == 0)
            {
                if (dfs(i, adj, vis) == true)
                return true;
            }
        }
        return false;
    }
};

//{ Driver Code Starts.

int main() {

    int t;
    cin >> t;
    while (t--) {
        int V, E;
        cin >> V >> E;

        vector<int> adj[V];

        for (int i = 0; i < E; i++) {
            int u, v;
            cin >> u >> v;
            adj[u].push_back(v);
        }

        Solution obj;
        cout << obj.isCyclic(V, adj) << "\n";
    }

    return 0;
}

// } Driver Code Ends