fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. class Graph
  4. {
  5.     int V;
  6.     list<int> *adj;
  7. public :
  8.     Graph(int V);
  9.     void addEdge(int v,int w);
  10.     bool isCyclic();
  11. };
  12. vector<int> g[100001];
  13. Graph::Graph(int V)
  14. {
  15.     this->V = V;
  16.     adj = new list<int>[V];
  17. }
  18. void Graph::addEdge(int v,int w)
  19. {
  20.     adj[v].push_back(w);
  21.     adj[w].push_back(v);
  22. }
  23. int main()
  24. {
  25.     int T;
  26.     cin>>T;
  27.     while(T--)
  28.     {
  29.         int _size,N;
  30.         cin>>_size>>N;
  31.         Graph *g = new Graph(_size);
  32.         for(int i=0;i<N;i++)
  33.         {
  34.             int u,v;
  35.             cin>>u>>v;
  36.             g->addEdge(u,v);
  37.         }
  38.         cout<<g->isCyclic()<<endl;
  39.     }
  40. }
  41.  
  42. bool isutil(list<int>*adj, int i, bool vis[],int V)
  43. {
  44.     int parent[V];
  45.     memset(parent,-1,sizeof(parent));
  46.     queue<int>q;
  47.     q.push(i);
  48.     vis[i] = true;
  49.     while(!q.empty())
  50.     {
  51.         int x = q.front();
  52.         q.pop();
  53.         for(auto u:adj[x])
  54.         {
  55.             if(!vis[u])
  56.             {
  57.                 vis[u] = true;
  58.                 q.push(u);
  59.                 parent[u]=x;
  60.             }
  61.             else if(parent[x]!=u)
  62.                 return true;
  63.         }
  64.     }
  65.     return false;
  66. }
  67.  
  68. bool Graph :: isCyclic()
  69. {
  70.     bool *vis = new bool[V];
  71.     for(int i=0;i<V;i++)
  72.         vis[i]=false;
  73.     for(int i=0;i<V;i++)
  74.     {
  75.         if(!vis[i] && isutil(adj,i,vis,V))
  76.             return true;
  77.     }
  78.     return false;
  79. }
Success #stdin #stdout 0s 17584KB
comments (?)
stdin
copy 
2
2 2
0 1 0 0
4 3
0 1 1 2 2 3
stdout
copy 
1
0
https://ideone.com/V4VWcW
language:
C++14 (gcc 8.3)
created:
5 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!