fork(6) download
copy 
  1. /*
  2.     Author : RAJON BARDHAN
  3.     AUST CSE 27th Batch
  4.     All my programming success are dedicated to my mom , dad , little sister madhobi , teachers , friends and love TANIA SULTANA RIMY
  5.  
  6.     ALGORITHM : SCC
  7. */
  8.  
  9. #include <bits/stdc++.h>
  10. using namespace std;
  11.  
  12. #define pb push_back
  13. #define ff first
  14. #define ss second
  15. #define mp make_pair
  16. #define memo(a,b) memset(a,b,sizeof(a))
  17. #define INF 1e9
  18. #define EPS 1e-8
  19. #define PI 3.14159265358979323846
  20. #define maxi 90000
  21.  
  22. typedef long long ll ;
  23. typedef unsigned long long ull ;
  24.  
  25. /* int dx[] = {1,-1,0,0} , dy[] = {0,0,1,-1}; */ // 4 Direction
  26. /* int dx[] = {1,-1,0,0,1,1,-1,-1} , dy[] = {0,0,1,-1,1,-1,1,-1}; */ // 8 Direction
  27. /* int dx[] = {1,-1,1,-1,2,2,-2,-2} , dy[] = {2,2,-2,-2,1,-1,1,-1}; */ // Knight Direction
  28. /* int dx[] = {2,-2,1,1,-1,-1} , dy[] = {0,0,1,-1,1,-1}; */ // Hexagonal Direction
  29. int N , M , t , cycle , dt[maxi+10] , ft[maxi+10] , ct[maxi+10] , cycleSize[maxi+10] , outdegree[maxi+10] , dp[maxi+10] , check[maxi+10] ;
  30. bool visit[maxi+10] ;
  31. vector <int> G[maxi+10] , GT[maxi+10] , Q ;
  32. void dfs1(int u)
  33. {
  34.     visit[u] = true ;
  35.     dt[u] = ++t ;
  36.     for(int i=0;i<G[u].size();i++)
  37.     {
  38.         int v = G[u][i] ;
  39.         if(!visit[v]) dfs1(v);
  40.     }
  41.     ft[u] = ++t ;
  42.     Q.pb(u);
  43. }
  44. void dfs2(int u,int cmp)
  45. {
  46.     visit[u] = false ;
  47.     ct[u] = cycle ;
  48.     cycleSize[cycle]++;
  49.     for(int i=0;i<GT[u].size();i++)
  50.     {
  51.         int v = GT[u][i] ;
  52.         if(visit[v]&&cmp>ft[v]) dfs2(v,cmp);
  53.     }
  54. }
  55. int dfs3(int u,int prev)
  56. {
  57.     check[ct[u]] = prev ;
  58.     if(dp[ct[u]]!=-1) return dp[ct[u]] ;
  59.     dp[ct[u]] = cycleSize[ct[u]] ;
  60.     for(int i=0;i<GT[u].size();i++)
  61.     {
  62.         int v = GT[u][i] ;
  63.         if(ct[u]!=ct[v]&&check[ct[v]]!=prev) dp[ct[u]]+=dfs3(v,prev);
  64.     }
  65.     return dp[ct[u]] ;
  66. }
  67. void Reset()
  68. {
  69.     t = 0 ;
  70.     cycle = 1 ;
  71.     Q.clear();
  72.     for(int i=0;i<=maxi;i++)
  73.     {
  74.         G[i].clear();
  75.         GT[i].clear();
  76.         cycleSize[i] = 0 ;
  77.         outdegree[i] = 0 ;
  78.         check[i] = 0 ;
  79.         dp[i] = -1 ;
  80.         visit[i] =  false ;
  81.     }
  82. }
  83. int main()
  84. {
  85.     //freopen("input.txt","r",stdin);
  86.     //freopen("output.txt","w",stdout);
  87.     int T ;
  88.     scanf("%d",&T);
  89.     while( T-- )
  90.     {
  91.         Reset();
  92.         scanf("%d%d",&N,&M);
  93.         while( M-- )
  94.         {
  95.             int A , B ;
  96.             scanf("%d%d",&A,&B);
  97.             G[A].pb(B);
  98.             GT[B].pb(A);
  99.         }
  100.         for(int i=1;i<=N;i++) if(!visit[i]) dfs1(i);
  101.         for(int i=Q.size()-1;i>=0;i--) if(visit[Q[i]]) { dfs2(Q[i],ft[Q[i]]); cycle++; }
  102.         for(int u=1;u<=N;u++)
  103.         {
  104.             for(int i=0;i<G[u].size();i++)
  105.             {
  106.                 int v = G[u][i] ;
  107.                 if(ct[u]!=ct[v]) outdegree[ct[u]]++;
  108.             }
  109.         }
  110.         int mx = 0 ;
  111.         set < pair<int,int> > S ;
  112.         for(int i=1;i<=N;i++)
  113.         {
  114.             if(outdegree[ct[i]]==0)
  115.             {
  116.                 int t = dfs3(i,i) ;
  117.                 S.insert(mp(i,t));
  118.                 mx=max(mx,t);
  119.             }
  120.         }
  121.         bool flag = true ;
  122.         for(auto i:S)
  123.         {
  124.             if(i.ss==mx)
  125.             {
  126.                 if(flag) flag = false ; else printf(" ");
  127.                 printf("%d",i.ff);
  128.             }
  129.         }
  130.         puts("");
  131.     }
  132.     return 0;
  133. }
  134.  
Success #stdin #stdout 0s 7892KB
comments (?)
stdin
copy 
4

6 5
1 2
2 3
3 1
1 4
5 6

5 5
1 2
2 3
3 4
4 5
5 4

4 4
1 2
2 3
3 4
4 1

5 4
3 1
3 2
4 3
5 3
stdout
copy 
4
4 5
1 2 3 4
1 2
https://ideone.com/5WMx0q
language:
C++14 (gcc 8.3)
created:
9 years 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!