fork download
copy 
  1. #include<bits/stdc++.h>
  2. #define int long long
  3. using namespace std;
  4.  
  5. int t, n, m;
  6. vector<int> p[100001];
  7. stack<int> st;
  8. int low[100001], num[100001], dele[100001], cc = 0, scc = 0;
  9.  
  10. void nhap() {
  11.     cin >> n >> m;
  12.     for (int i = 1; i <= m; i++) {
  13.         int a, b;
  14.         cin >> a >> b;
  15.         p[a].push_back(b);
  16.     }
  17. }
  18.  
  19. void dfs(int u) {
  20.     num[u] = low[u] = ++cc;
  21.     st.push(u);
  22.     for (int v : p[u]) {
  23.         if (dele[v]) continue;
  24.         if (!num[v]) {
  25.             dfs(v);
  26.             low[u] = min(low[u], low[v]);
  27.         } else
  28.             low[u] = min(low[u], num[v]);
  29.     }
  30.     if (num[u] == low[u]) {
  31.         scc++;
  32.         while (!st.empty()) {
  33.             int v = st.top();
  34.             st.pop();
  35.             dele[v] = scc;
  36.             if (v == u) break;
  37.         }
  38.     }
  39. }
  40.  
  41. signed main() {
  42.     cin >> t;
  43.     while (t--) {
  44.         nhap();
  45.         cc = scc = 0;
  46.         fill(num, num + n + 1, 0);
  47.         fill(low, low + n + 1, 0);
  48.         fill(dele, dele + n + 1, 0);
  49.         for (int i = 1; i <= n; i++) {
  50.             if (!num[i]) dfs(i);
  51.         }
  52.         if (scc == 1) cout << "NO" << "\n";
  53.         else cout << "YES" << "\n";
  54.         for (int i = 1; i <= n; i++) {
  55.             p[i].clear();
  56.         }
  57.     }
  58. }
  59.  
Success #stdin #stdout 0.01s 7688KB
comments (?)
stdin
copy 
2
3 3
1 2
2 3
3 1
3 2
1 2
2 3
stdout
copy 
NO
YES
https://ideone.com/7NmNVB
language:
C++14 (clang 8.0)
created:
257 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!