SHARE
TWEET

SCC( tarjan )

LinKin Feb 5th, 2012 2,209 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. /*
  2.  * Strongly Connected Component
  3.  * Algorithm : Tarjan's Algorithm
  4.  * Order : O( V+E )
  5.  */
  6. #include<stdio.h>
  7. #include<string.h>
  8. #include<vector>
  9. #include<stack>
  10. #include<algorithm>
  11. using namespace std;
  12. #define MAX 4007
  13. #define pb push_back
  14. long N,M;
  15. vector<long> edge[MAX+7];
  16. bool visit[MAX+7];
  17. bool instk[MAX+7];
  18. long low[MAX+7],I;
  19. long ind[MAX+7];
  20. stack<long> stk;
  21. void SCC( long u ){
  22.     visit[u] = true;
  23.     instk[u] = true;
  24.     ind[u] = ++I;
  25.     low[u] = I;
  26.     stk.push( u );
  27.     long i;
  28.     for( i=0;i<edge[u].size();i++){
  29.         long v = edge[u][i];
  30.         if( !visit[v] ){
  31.             SCC( v );
  32.             low[u] = min( low[u],low[v] );
  33.         }
  34.         else if( instk[v] ){
  35.             low[u] = min( low[u],ind[v] );
  36.         }
  37.     }
  38.     if( low[u]!=ind[u] ) return;
  39.     // found new component
  40.     while( stk.top()!=u ){
  41.         long v = stk.top();
  42.         stk.pop();
  43.         instk[v] = false;
  44.     }
  45.     stk.pop();
  46.     instk[u] = false;
  47. }
  48.  
  49. int main( void )
  50. {
  51.     long i,j,u,v,Icase,k = 0;
  52.     //freopen("text1.txt","r",stdin );
  53.     scanf("%ld%ld",&N,&M );
  54.     for( i=1;i<=M;i++){
  55.         scanf("%ld%ld",&u,&v );
  56.         edge[u].pb( v );
  57.     }
  58.     for( i=1;i<=N;i++){
  59.         if( visit[i] ) continue;
  60.         SCC( i );
  61.     }
  62.     return 0;
  63. }
RAW Paste Data
Top