DuongNhi99

NKONEARC

Dec 2nd, 2020 (edited)
107
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.92 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. #define ll long long
  3. using namespace std;
  4.  
  5. const int N = 2005;
  6.  
  7. int n, m;
  8. vector<int> a[N];
  9.  
  10. int cnt, SCC, top;
  11. int low[N], id[N], st[N], SCC_id[N], in[N], out[N];
  12. bool visited[N];
  13.  
  14. void Tarjan(int u) {
  15.     low[u] = id[u] = ++cnt;
  16.     st[++top] = u;
  17.  
  18.     for(int v : a[u]) {
  19.         if(visited[v]) continue;
  20.  
  21.         if(id[v] != 0)
  22.             low[u] = min(low[u], id[v]);
  23.         else {
  24.             Tarjan(v);
  25.             low[u] = min(low[u], low[v]);
  26.         }
  27.     }
  28.  
  29.     if(id[u] == low[u]) {
  30.         SCC++;
  31.         int v;
  32.         while(v != u) {
  33.             v = st[top--];
  34.             SCC_id[v] = SCC;
  35.             visited[v] = true;
  36.         }
  37.     }
  38. }
  39.  
  40. int main()
  41. {
  42.     //freopen("in.txt", "r", stdin);
  43.     //freopen("NKONEARC .inp", "r", stdin);
  44.     //freopen("NKONEARC .out", "w", stdout);
  45.     ios_base::sync_with_stdio(false);
  46.     cin.tie(NULL); cout.tie(NULL);
  47.  
  48.     cin >> n >> m;
  49.     for(int i = 1; i <= m; i++) {
  50.         int u, v;; cin >> u >> v;
  51.         a[u].push_back(v);
  52.     }
  53.  
  54.     for(int i = 1; i <= n; i++)
  55.         if(id[i] == 0)
  56.             Tarjan(i);
  57.  
  58.     for(int u = 1; u <= n; u++)
  59.         for(int v : a[u]) {
  60.             if(SCC_id[u] != SCC_id[v]) {
  61.                 ++in[SCC_id[v]];
  62.                 ++out[SCC_id[u]];
  63.             }
  64.         }
  65.  
  66.     int source = 0, sink = 0;
  67.     int s = -1, t = -1;
  68.     for(int i = 1; i <= SCC; i++) {
  69.         if(in[i] == 0)
  70.             source++, s = i;
  71.  
  72.         if(out[i] == 0)
  73.             sink++, t = i;
  74.     }
  75.  
  76.     if(source != 1 || sink != 1)
  77.         cout << "NO" << '\n';
  78.     else {
  79.         cout << "YES" << '\n';
  80.  
  81.         for(int i = 1; i <= n; i++)
  82.             if(SCC_id[i] == s) {
  83.                 s = i; break;
  84.         }
  85.         for(int i = 1; i <= n; i++)
  86.             if(SCC_id[i] == t) {
  87.                 t = i; break;
  88.         }
  89.         cout << t << ' ' << s << '\n';
  90.     }
  91.  
  92.     return 0;
  93. }
Advertisement
Add Comment
Please, Sign In to add comment