Advertisement
spider68

DFS direct graph cycle

Jul 12th, 2021
748
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.64 KB | None | 0 0
  1. class Solution
  2. {
  3.     public:
  4. bool dfs(int i,int vis[],int present[],vector<int>adj[]){
  5.     if(vis[i]==false){
  6.         vis[i]=1,present[i]=1;
  7.         for(auto x:adj[i]){
  8.             if(vis[x]==1 && present[x]==1)return true;
  9.             else if(vis[x]==0 && dfs(x,vis,present,adj)==true)return true;
  10.         }
  11.     }
  12.    
  13.     present[i]=0;
  14.     return false;
  15. }
  16. bool isCyclic(int V, vector<int> adj[])
  17. {
  18.     int vis[V],present[V];
  19.     for(int i=0;i<V;i++)vis[i]=0,present[i]=0;
  20.     for(int i=0;i<V;i++)
  21.     {
  22.         if(vis[i]==0)
  23.         {
  24.             if(dfs(i,vis,present,adj)==true)return true;
  25.         }
  26.     }
  27.     return false;
  28. }
  29. };
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement