fork download
copy 
  1. #include<bits/stdc++.h>
  2. #define int long long
  3. using namespace std;
  4.  
  5. int n, m;
  6. vector<int> p[200001];
  7. int low[200001], num[200001], dele[200001], lead[200001], cc = 0, scc = 0, lc[200001], tplt = 0, db[200001];
  8. stack<int> st;
  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.     low[u] = num[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.         lead[scc] = u;
  33.         while (true) {
  34.             int v = st.top();
  35.             st.pop();
  36.             dele[v] = scc;
  37.             if (v == u) break;
  38.         }
  39.     }
  40. }
  41.  
  42. signed main() {
  43.     nhap();
  44.     for (int i = 1; i <= n; i++) {
  45.         if (!num[i]) {
  46.             tplt++;
  47.             db[tplt] = i;
  48.             dfs(i);
  49.         }
  50.     }
  51.     for (int i = 1; i <= n; i++) {
  52.         for (int v : p[i]) {
  53.             if (dele[v] != dele[i]) {
  54.                 lc[dele[v]]++;
  55.             }
  56.         }
  57.     }
  58.     int ans = 0;
  59.     for (int i = 1; i <= scc; i++) {
  60.         if (lc[i] != 0) ans++;
  61.     }
  62.     if (tplt >= 2) {
  63.         cout << "NO" << "\n";
  64.         cout << db[1] << " " << db[2];
  65.     }
  66.     else
  67.     {
  68.         if (ans == 0)
  69.         cout << "YES";
  70.         else if (ans > 0) {
  71.         cout << "NO" << "\n";
  72.         int c = 0, d = 0;
  73.         for (int i = 1; i <= scc; i++) {
  74.             if (lc[i] != 0 && c == 0) {
  75.                 cout << lead[i] << " ";
  76.                 c = 1;
  77.             }
  78.             if (lc[i] == 0 && d == 0) {
  79.                 cout << lead[i] << " ";
  80.                 d = 1;
  81.             }
  82.         }
  83.     }
  84.     }
  85. }
  86.  
Success #stdin #stdout 0.01s 11720KB
comments (?)
stdin
copy 
4 5
1 2
2 3
3 1
1 4
3 4
stdout
copy 
NO
4 1
https://ideone.com/NAXLGq
language:
C++14 (clang 8.0)
created:
259 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!