Tarjan算法——强连通分量

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 
 4 const int maxn=100000+15;
 5 const int maxm=100000+15;
 6 struct Edge
 7 {
 8     int x,y,next;
 9     Edge(int x=0,int y=0,int next=0):x(x),y(y),next(next) {} 
10 }edge[maxm];
11 int sumedge,head[maxn]; 
12 int n,m;
13 int ins(int x,int y)
14 {
15     edge[++sumedge]=Edge(x,y,head[x]);
16     return head[x]=sumedge;
17 }
18 int tim,dfn[maxn],low[maxn],Stack[maxn],top,color[maxn],sumc;
19 int state[maxn];
20 int dfs(int now)
21 {
22     state[now]=1;
23     dfn[now]=++tim;
24     low[now]=dfn[now];
25     Stack[++top]=now;
26     for (int u=head[now];u;u=edge[u].next)
27      if (state[edge[u].y]==0)
28      {
29          dfs(edge[u].y);
30          low[now]=min(low[now],low[edge[u].y]);
31       } 
32       else 
33       if (state[edge[u].y]==1)
34        low[now]=min(low[now],dfn[edge[u].y]);
35     if (dfn[now]==low[now])
36     {
37         sumc++;
38         for (;Stack[top]!=now;top--)
39         {
40             color[Stack[top]]=sumc;
41             state[Stack[top]]=2;
42         }
43         color[now]=sumc;
44         state[now]=2;
45         top--;
46     }
47     return 0;
48 }
49 int main()
50 {
51     scanf("%d%d",&n,&m);
52     for (int i=1;i<=m;i++)
53     {
54         int x,y;
55         scanf("%d%d",&x,&y);
56         ins(x,y); 
57     } 
58     dfs(1);
59     for (int i=1;i<=n;i++) printf("%d ",color[i]);
60     printf("\n");
61     return 0;
62  }