tarjian求强联通分量

 1 //求强联通分量 
 2 #include<bits/stdc++.h>
 3 const int N=1e5+7;
 4 const int M=1e5+7;
 5 struct node{
 6     int v,next;
 7 }e[M];
 8 int head[N],cnt;
 9 int p[N],st[N],id,top,scc;
10 int dfn[N],low[N],belong[N];
11 void add(int u,int v){
12     e[cnt].v=v,e[cnt].next=head[u];
13     head[u]=cnt++;
14 }
15 void init(){
16     memset(head,-1,sizeof(head));
17     memset(p,0,sizeof(p));
18     memset(dfn,0,sizeof(dfn));
19     id=top=cnt=0;
20 }
21 void dfs(int u){
22     dfn[u]=low[u]=++id;
23     st[++top]=u;p[u]=1;
24     int v;
25     for(int i=head[u];i!=-1;i=e[i].next){
26         v=e[i].v;
27         if(!dfn[v]){
28             dfs(v);
29             if(low[v]<low[u])low[u]=low[v];
30         }else if(p[v]&&dfn[v]<low[u]){
31             low[u]=dfn[v];
32         }
33     }
34     if(dfn[u]==low[u]){
35         ++scc;
36         do{
37             v=st[top--];
38             p[v]=0;
39             belong[v]=scc;
40         }while(v!=u);
41     }
42 }
43 void Tarjian(int n){
44     for(int i=1;i<=n;i++){
45         if(!dfn[i])
46             dfs(i);
47     }
48     printf("%d
",scc);
49     for(int i=1;i<=n;i++){
50         printf("%d %d
",i,belong[i]);
51     }
52 }
53 int main(){
54     int n,m,u,v;
55     scanf("%d%d",&n,&m);
56     init();
57     while(m--){
58         scanf("%d%d",&u,&v);
59         add(u,v);
60     }
61     Tarjian(n);
62 }