fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3.  
  4. vector<long long> a[100005];
  5. long long n,m;
  6. long long visited[100005];
  7. bool check=true;
  8.  
  9. void bfs(long long x, vector<long long> a[], long long visited[], bool &check)
  10. {
  11.     queue<long long> q;
  12.  
  13.     q.push(x);
  14.     visited[x]=1;
  15.  
  16.     while (!q.empty())
  17.     {
  18.         long long u = q.front();
  19.         q.pop();
  20.  
  21.         for (long long v : a[u])
  22.         {
  23.             if (visited[v]==0)
  24.             {
  25.                 visited[v] = 3 - visited[u];
  26.                 q.push(v);
  27.             }
  28.             else if (visited[v]==visited[u])
  29.             {
  30.                 check=false;
  31.                 return;
  32.             }
  33.         }
  34.     }
  35. }
  36.  
  37. void input()
  38. {
  39.     cin>>n>>m;
  40.  
  41.     for (long long i=1;i<=m;i++)
  42.     {
  43.         long long u,v;
  44.  
  45.         cin>>u>>v;
  46.  
  47.         a[u].push_back(v);
  48.         a[v].push_back(u);
  49.     }
  50. }
  51.  
  52. void solve()
  53. {
  54.     for (long long i=1;i<=n;i++)
  55.     {
  56.         if (visited[i]==0)
  57.         {
  58.             bfs(i,a,visited,check);
  59.  
  60.             if (!check)
  61.             {
  62.                 cout<<"NO";
  63.                 return;
  64.             }
  65.         }
  66.     }
  67.  
  68.     cout<<"YES";
  69. }
  70.  
  71. int main()
  72. {
  73.     ios_base::sync_with_stdio(0);
  74.     cin.tie(0);
  75.  
  76.     input();
  77.     solve();
  78. }
  79.  
Success #stdin #stdout 0.01s 6232KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
YES
https://ideone.com/6418Ph
language:
C++14 (gcc 8.3)
created:
2 days 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!