Saved Bookmarks
| 1. |
Write a function to detect cycle in an undirected graph |
Answer»
From the above representation, we can see that there exists a cycle: 1→2→3→1 //function to run dfs for a given node in the graphint dfs(int v,vector<int> adj[],vector<int> &visited,vector<int> &rec,int i,int parent){ int ans=0; visited[i]=1; rec[i]=1; for(auto x : adj[i]){ if(x!=parent) { if(rec[x]) return 1; ans=dfs(v,adj,visited,rec,x,i); if(ans) return 1; } } rec[i]=0; return 0; } // Function to detect cycle in an undirected graph. // it takes adjacency list representation as an argument bool isCycle(int v, vector<int> adj[]) { vector<int> visited(v,0),rec(v,0); int ans=0; for(int i=0;i<v;i++){ if(visited[i]==0) ans=dfs(v,adj,visited,rec,i,-1); if(ans) return 1; } return 0; }
|
|