SHARE
TWEET

Untitled

a guest Jan 15th, 2020 61 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. typedef long long ll;
  6. const ll N = 1e5 + 5;
  7.  
  8. vector<ll> v1[N];
  9. vector<ll> v2[N];
  10. vector<ll> v[N];
  11. vector<ll> ts;
  12. ll was[N];
  13.  
  14. void dfs1(int pos)
  15. {
  16.     was[pos] = 1;
  17.     for(ll x : v1[pos])
  18.         if(!was[pos])
  19.             dfs1(x);
  20.     ts.push_back(pos);
  21. }
  22.  
  23. void dfs2(int pos, int color)
  24. {
  25.     was[pos] = color;
  26.     for(ll x : v2[pos])
  27.         if(!was[x])
  28.             dfs2(x, color);
  29. }
  30.  
  31. int main ()
  32. {
  33.     ll L[N], R[N];
  34.     ll n, m;
  35.     cin >> n >> m;
  36.     for(int i = 0; i < m; i++)
  37.     {
  38.         ll l, r;
  39.         cin >> l >> r;
  40.         v1[l].push_back(r);
  41.         v2[r].push_back(l);
  42.         L[i] = l;
  43.         R[i] = r;
  44.     }
  45.     for(int i = 0; i < n; i++)
  46.         if(!was[i])
  47.             dfs1(i);
  48.     reverse(ts.begin(), ts.end());
  49.     ll color = 1;
  50.     for(int i = 0; i < n; i++)
  51.         was[i] = 0;
  52.     for(int i : ts)
  53.         if(!was[i])
  54.             dfs2(i, color++);
  55.     for(int i = 0; i < m; i++)
  56.     {
  57.         ll l = L[i], r = R[i];
  58.         if(was[l] != was[r])
  59.         {
  60.             int l1 = was[l];
  61.             int r1 = was[r];
  62.             v[l1].push_back(r1);
  63.         }
  64.     }
  65.     for(int i = 1; i < color; i++)
  66.     {
  67.         cout << i << " : ";
  68.         for(int x : v[i])
  69.             cout << x << ' ';
  70.         cout << '\n';
  71.     }
  72. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!
 
Top