Tarjan 求强连通分量 C++模板

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 const int maxn=5005;
 4 int N,M;
 5 int stac[maxn],top=0;//Tarjan算法中的栈
 6 bool instac[maxn];//检查是否在栈中
 7 int dfn[maxn];//深度优先搜索访问次序
 8 int low[maxn];//能追溯到的最早的次序
 9 int tot=0;//有向图强连通分量个数
10 int index=0;//索引号
11 vector<int>to[maxn];
12 vector<int> kin[maxn];//获得强连通分量结果
13 int inkin[maxn];//记录每个点在第几号强连通分量里
14 
15 inline void tarjan(int x){
16     dfn[x]=low[x]=index++;
17     stac[++top]=x;
18     instac[x]=true;
19     for(int i=0;i<to[x].size();i++){
20         int y=to[x][i];
21         if(dfn[y]==-1){
22             tarjan(y);
23             low[x]=min(low[x],low[y]);
24         }
25         else if(instac[y]!=0){
26             low[x]=min(low[x],dfn[y]);
27         }
28     }
29     if(dfn[x]==low[x]){
30         tot++;
31         int y;
32         do{
33             y=stac[top--];
34             instac[y]=false;
35             kin[tot].push_back(y);
36             inkin[y]=tot;
37         }while(y!=x);
38     }
39 }
40 int main(){
41     scanf("%d%d",&N,&M);
42     for(int i=1;i<=M;i++){
43         int u,v;
44         scanf("%d%d",&u,&v);
45         to[u].push_back(v);
46     }
47     memset(dfn,-1,sizeof(dfn));
48     tarjan(1);
49     for(int i=1;i<=N;i++){//输出分组 
50         cout<<inkin[i]<<endl;
51     }
52     return 0;
53 }