fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3.  
  4. const long long MaxN = 2e5 + 5;
  5.  
  6. vector<long long> a[MaxN];
  7. long long mark[MaxN];
  8. long long n,m;
  9.  
  10. bool dfs(long long s)
  11. {
  12.     stack<pair<long long,long long>> st;
  13.  
  14.     st.push({s,0});
  15.     mark[s] = 1;
  16.  
  17.     while (!st.empty())
  18.     {
  19.         long long u = st.top().first;
  20.         long long i = st.top().second;
  21.  
  22.         if (i == a[u].size())
  23.         {
  24.             mark[u] = 2;
  25.             st.pop();
  26.             continue;
  27.         }
  28.  
  29.         long long v = a[u][i];
  30.         st.top().second++;
  31.  
  32.         if (mark[v] == 1)
  33.             return true;
  34.  
  35.         if (mark[v] == 0)
  36.         {
  37.             mark[v] = 1;
  38.             st.push({v,0});
  39.         }
  40.     }
  41.  
  42.     return false;
  43. }
  44.  
  45. int main()
  46. {
  47.     ios::sync_with_stdio(0);
  48.     cin.tie(0);
  49.  
  50.     cin >> n >> m;
  51.  
  52.     for (long long i=1;i<=m;i++)
  53.     {
  54.         long long u,v;
  55.         cin >> u >> v;
  56.         a[u].push_back(v);
  57.     }
  58.  
  59.     for (long long i=1;i<=n;i++)
  60.     {
  61.         if (mark[i]==0)
  62.         {
  63.             if (dfs(i))
  64.             {
  65.                 cout << "YES";
  66.                 return 0;
  67.             }
  68.         }
  69.     }
  70.  
  71.     cout << "NO";
  72. }
Success #stdin #stdout 0.01s 8932KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
NO
https://ideone.com/SJMbYb
language:
C++14 (gcc 8.3)
created:
9 hours 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!