SCC( tarjan )


SUBMITTED BY: Guest

DATE: Nov. 12, 2013, 2:45 a.m.

FORMAT: Text only

SIZE: 1.5 kB

HITS: 781

  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. {
  23. Visit[u] = true;
  24. InStk[u] = true;
  25. Ind[u] = ++I;
  26. Low[u] = I;
  27. Stk.push( u );
  28. long i;
  29. for( i=0;i<Edge[u].size();i++){
  30. long v = Edge[u][i];
  31. if( !Visit[v] ){
  32. SCC( v );
  33. Low[u] = min( Low[u],Low[v] );
  34. }
  35. else if( InStk[v] ){
  36. Low[u] = min( Low[u],Ind[v] );
  37. }
  38. }
  39. if( Low[u]!=Ind[u] ) return;
  40. // found new component
  41. while( Stk.top()!=u ){
  42. long v = Stk.top();
  43. Stk.pop();
  44. InStk[v] = false;
  45. }
  46. Stk.pop();
  47. InStk[u] = false;
  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. }

comments powered by Disqus