daily pastebin goal
41%
SHARE
TWEET

Untitled

a guest Mar 18th, 2019 56 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2. #define eb emplace_back
  3. #define maxn 10005
  4. using namespace std;
  5. vector<int> G[maxn], rG[maxn], nG[maxn], fini;
  6. int vis[maxn], T, scc[maxn], sz[maxn], ans, in[maxn];
  7. void dfs1 ( int x ){
  8.     vis[x] = T;
  9.     for ( int i : G[x] )
  10.         if ( vis[i]!=T ) dfs1(i);
  11.     fini.eb(x);
  12. }
  13. void dfs2 ( int x, int cnt ){
  14.     vis[x] = T;
  15.     scc[x] = cnt;
  16.     sz[cnt]++;
  17.     for ( int i : rG[x] )
  18.         if ( vis[i]!=T ) dfs2(i, cnt);
  19. }
  20. void dfs3 ( int x, int cnt ){
  21.     ans = max(ans, cnt);
  22.     for ( int i : nG[x] )
  23.         if ( vis[i]!=T ) {
  24.             vis[i] = T;
  25.             dfs3(i, cnt+sz[i]);
  26.             vis[i] = 0;
  27.         }
  28. }
  29. int main(){
  30.     ios::sync_with_stdio ( false );
  31.     cin.tie(0);
  32.     int t, n, m, a, b, scnt;   
  33.     cin >> t;
  34.     while ( t-- ){
  35.         cin >> n >> m;
  36.         for ( int i=0; i<=n; ++i )
  37.             G[i].clear(), rG[i].clear(), nG[i].clear();
  38.         fini.clear();
  39.         while ( m-- ){
  40.             cin >> a >> b;
  41.             G[a].eb(b);
  42.             rG[b].eb(a);
  43.         }
  44.         T++;
  45.         for ( int i=1; i<=n; ++i )
  46.             if ( vis[i]!=T ) dfs1(i);
  47.         T++; scnt = 0; memset(sz, 0, sizeof sz);
  48.         for ( int i=fini.size()-1; i>=0; --i )
  49.             if ( vis[fini[i]]!=T ) dfs2(fini[i], ++scnt);
  50.         memset(in, 0, sizeof in);
  51.         for ( int i=1; i<=n; ++i )
  52.             for ( int j : G[i] )
  53.                 if ( scc[i]!=scc[j] ){
  54.                     nG[scc[i]].eb(scc[j]);
  55.                     in[scc[j]]++;
  56.                 }
  57.         ans = 0;
  58.         for ( int i=1; i<=scnt; ++i )
  59.             if ( !in[i] ) { T++, dfs3(i, sz[i]); }
  60.         cout << ans << '\n';
  61.     }
  62.     return 0;
  63. }
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
 
Top