fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. //variable
  4. #define ld long double
  5. #define ll long long
  6. #define db double
  7. #define ii pair<int,int>
  8. #define f first
  9. #define s second
  10. #define mp make_pair
  11. #define mt make_tuple
  12. //vector
  13. #define pb push_back
  14. #define all(v) v.begin(),v.end()
  15. #define len(a) (int)a.length()
  16. #define sz(a) (int)a.size()
  17. //mask
  18. #define BIT(i) (1LL<<(i))
  19. //better code, debugger
  20. #define watch(n) cerr << #n << ": " << n << endl
  21. #define debug(x) for (auto p: x) cerr<<p<<' ';cerr<<endl
  22. #define forw(i,j,z) for(int i=(int)j;i<=(int)z;i++)
  23. #define ford(i,j,z) for (int i=(int)j;i>=(int)z;i--)
  24. #define fIlE "."
  25. //auto seed = chrono::high_resolution_clock::now().time_since_epoch().count();
  26. //mt19937 RAND(seed);
  27. const int mod = 998244353;
  28. inline int add(int u,int v){u+=v;if(u>=mod)u-=mod;return u;}
  29. inline int dec(int u,int v){u-=v;if(u<0)u+=mod;return u;}
  30. inline int mul(int u,int v){return (ll)u*v%mod;}
  31. const ii inf = mp(-1, -1);
  32. ii ans = inf;
  33. const int N = 1e5 + 1;
  34. int num[N], low[N];
  35. vector<int> a[N];
  36. int timedfs = 0, timedfs2 = 0;
  37. int n, m;
  38. stack<int> haha;
  39. int id[N];
  40. bool del[N];
  41.  
  42. void dfs(int u)
  43. {
  44.     num[u] = low[u] = ++timedfs;
  45.     haha.push(u);
  46.     for (int v : a[u]){
  47.         if (del[v]) continue;
  48.         if (!num[v]){
  49.             dfs(v);
  50.             low[u] = min(low[u], low[v]);
  51.         }
  52.         else low[u] = min(low[u], num[v]);
  53.     }
  54.     if (low[u] >= num[u])
  55.     {
  56.         int id_group = ++timedfs2;
  57.         while(!haha.empty() && low[u] >= num[u])
  58.         {
  59.             int v = haha.top();
  60.             del[v] = 1;
  61.             haha.pop();
  62.             id[v] = id_group;
  63.             if (v == u) break;
  64.         }
  65.     }
  66. }
  67. void solve()
  68. {
  69.     cin >> n >> m;
  70.     forw(i, 1, m){
  71.         int u, v;
  72.         cin >> u >> v;
  73.         if (u == v) continue;
  74.         a[u].pb(v);
  75.     }
  76.     forw(i, 1, n) if (!num[i])
  77.         dfs(i);
  78.     if (timedfs2 > 1){
  79.         int u = 1;
  80.         forw(v, 2, n) if (id[u] != id[v]){
  81.             if (id[u] < id[v]) swap(u, v);
  82.             cout << "NO\n";
  83.             cout << v << ' ' << u;
  84.             return;
  85.         }
  86.     }
  87.     else cout << "YES";
  88. }
  89. signed main()
  90. {
  91.     ios_base::sync_with_stdio(false);
  92.     cin.tie(0);
  93.     if (fopen(fIlE"inp", "r"))
  94.         freopen(fIlE"inp","r",stdin), freopen(fIlE"out","w",stdout);
  95.     //time_t TIME_TU=clock();
  96.     int t=1;
  97. //    cin>>t;
  98.     while(t--)
  99.         solve();
  100.     //time_t TIME_TV=clock();
  101.     //cerr<<(db)(TIME_TV-TIME_TU)/CLOCKS_PER_SEC<<endl;
  102.     return 0;
  103. }
  104.  
Success #stdin #stdout 0.01s 6012KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
YES
https://ideone.com/xjTtgT
language:
C++ (gcc 8.3)
created:
4 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!