# SCC( tarjan )

Feb 5th, 2012
2,688
0
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. }