fork download
copy 
  1. #include<bits/stdc++.h>
  2. #include<iostream>
  3.  
  4. using namespace std;
  5.  
  6. int n,m;
  7.  
  8. int const N = 200005;
  9.  
  10. vector<int> v[N];
  11.  
  12. vector<bool> visited(N,false);
  13.  
  14. bool cycle = false;
  15.  
  16. void bfs(int i){
  17.     if(cycle)return;
  18.  
  19.     queue<pair<int,int>> q; // pair of <node,parent>
  20.  
  21.     q.push({i,-1});
  22.  
  23.     while(q.size()){
  24.         pair<int,int> it = q.front();q.pop();
  25.  
  26.         int node = it.first, parent = it.second;
  27.  
  28.         visited[node] = true;
  29.  
  30.         for(int w: v[node]){
  31.             if(w==parent)continue;
  32.             if(visited[w]){
  33.                 cycle = true;return;
  34.             }
  35.             q.push({w,node});
  36.         }
  37.     }
  38. }
  39.  
  40.  
  41. int main()
  42. {
  43.  
  44.     cin >> n >> m;
  45.  
  46.     while(m--){
  47.         int a,b;
  48.  
  49.         cin >> a >> b;
  50.  
  51.         v[a].push_back(b);
  52.         v[b].push_back(a);
  53.     }
  54.  
  55.     for(int i = 1;i<=n;i++){
  56.         if(cycle)break;
  57.         if(!visited[i]){
  58.             bfs(i);
  59.         }
  60.     }
  61.  
  62.     if(!cycle){
  63.         puts("NO");
  64.     }
  65.  
  66.     else{
  67.         puts("YES");
  68.     }
  69.  
  70. }
Success #stdin #stdout 0.01s 8256KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
NO
https://ideone.com/TWYllE
language:
C++14 (gcc 8.3)
created:
10 days ago
visibility:
secret

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!