Advertisement
vaibhav1906

Cycle in undirected graph

Jul 27th, 2021
128
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 0.90 KB | None | 0 0
  1. //Link to the question : https://practice.geeksforgeeks.org/problems/detect-cycle-in-an-undirected-graph/1
  2.  
  3. bool check(vector<int>adj[],vector<bool> &visit, int curr, int parent){
  4.  
  5. visit[curr] = true;
  6.  
  7. for(int i = 0 ; i< adj[curr].size(); i++){
  8. int ncurr = adj[curr][i];
  9. if(visit[ncurr]==false){
  10. if(check(adj,visit,ncurr,curr)==true)return true;
  11. }
  12. else{
  13. if(parent!=ncurr)return true;
  14. }
  15.  
  16. }
  17.  
  18. return false;
  19.  
  20. }
  21.  
  22. class Solution
  23. {
  24. public:
  25. //Function to detect cycle in an undirected graph.
  26. bool isCycle(int V, vector<int>adj[])
  27. {
  28. // Code here
  29. vector<bool> visit(V,false);
  30.  
  31. for(int i = 0; i<V; i++){
  32. if(visit[i]==false){
  33. if(check(adj,visit,i,-1)==true)return true;
  34. }
  35.  
  36. }
  37.  
  38. return false;
  39.  
  40. }
  41. };
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement