有向图的强连通分量 tarjan
作者:
zsfzmxl
,
2023-04-08 20:33:09
,
所有人可见
,
阅读 190
#include<bits/stdc++.h>
using namespace std;
const int N=500000;
int h[N],ne[N],to[N];
int dfn[N],low[N];
int n,m;
int idx,num,cnt,top;
int in[N],belong[N],sta[N];
void add(int a,int b){
to[++idx]=b;
ne[idx]=h[a];
h[a]=idx;
}
stack<int>q;
void tarjan(int x){
dfn[x]=low[x]=++num;
q.push(x);
in[x]=1;
for(int i=h[x];i!=-1;i=ne[i]){
int y=to[i];
if(!dfn[y]){
tarjan(y);
low[x]=min(low[x],low[y]);
}
else if(in[y]){
low[x]=min(low[x],dfn[y]);
}
}
if(low[x]==dfn[x]){
cnt++;
int y;
do{
y=q.top();
q.pop();
belong[y]=cnt;
in[y]=0;
}while(x!=y);
}
}
int main(){
memset(h,-1,sizeof h);
cin>>n>>m;
for(int i=1;i<=m;i++){
int a,b;
cin>>a>>b;
add(a,b);
}
for(int v=1;v<=n;v++){
if(dfn[v]==0)tarjan(v);
}
for(int i=1;i<=n;i++){
cout<<i<<":"<<dfn[i]<<" "<<low[i]<<endl;
}
return 0;
}