spider68

detect cycle in UnDirected

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