Advertisement
vaibhav1906

Cycles in undirected graph

Jan 11th, 2022
1,338
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.26 KB | None | 0 0
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. void addEdge(vector<int> adj[], int u, int v)
  4. {
  5.     adj[u].push_back(v);
  6.     adj[v].push_back(u);
  7. }
  8. int cycle(vector<int> adj[],vector<int> &vis,int x,int parent)
  9. {
  10.     vis[x]=1;
  11.     for(int i:adj[x])
  12.     {
  13.         if(vis[i]==0)
  14.         {
  15.             if(cycle(adj,vis,i,x))
  16.                 return 1;
  17.         }
  18.         else if(vis[i]==1 && i!=parent)
  19.             return 1;
  20.     }
  21.     return 0;
  22. }
  23. void printGraph(vector<int> adj[], int V)
  24. {
  25.     for (int v = 0; v < V; ++v)
  26.     {
  27.         cout << "Adjacency list of vertex "
  28.              << v << "\n";
  29.         for (auto x : adj[v])
  30.            cout << x <<" ";
  31.         cout<<"\n";
  32.     }
  33. }
  34. int main()
  35. {
  36.     int V = 5;
  37.     vector<int> adj[V];
  38.     addEdge(adj,0,1);
  39.     addEdge(adj,0,2);
  40.     addEdge(adj,0,3);
  41.     addEdge(adj,2,3);
  42.     addEdge(adj,3,4);
  43.     //printGraph(adj,V);
  44.     vector<int> vis(V,0);
  45.     int cyc=0;
  46.     for(int i=0;i<V;i++)
  47.     {
  48.         if(vis[i]==0)
  49.         {
  50.             if(cycle(adj,vis,i,-1))
  51.             {
  52.                 cout<<"The graph contains a cycle";
  53.                 cyc=1;
  54.                 break;
  55.             }
  56.         }
  57.     }
  58.     if(cyc==0)
  59.         cout<<"The graph does not contain a cycle";
  60.     return 0;
  61. }
  62.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement