有向图的强连通分量
作者:
qushuka
,
2022-05-10 19:27:00
,
所有人可见
,
阅读 194
#include<vector>
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 1e6+100;
int e[N],h[N],ne[N],idx;
int low[N],dfn[N],c[N];
int stack[N];
int ins[N];
vector<int> scc[N];
int n,m,num,top,cnt;
void add(int a,int b) {
e[++idx] = b,ne[idx] = h[a],h[a] = idx;
}
void tarjan(int x) {//代表第几个点在处理。递归的是点。
dfn[x] = low[x] = ++num;
stack[++top] = x, ins[x] = 1;//ins[x]表示x在栈里
for(int i = h[x]; i; i = ne[i]) {
int y = e[i];
if(!dfn[y]) {
tarjan(y);//往下进行延伸,开始递归
low[x] = min(low[x],low[y]);
} else if(ins[y])//如果访问过,并且还在栈里。
low[x] = min(low[x],dfn[y]);
}
if(dfn[x] == low[x]) {
cnt++;
int z;
do {
//cout << stack[top] << " ";
z = stack[top--],ins[z] = 0;
c[z] = cnt;
scc[cnt].push_back(z);
} while(x != z);//出栈
//cout << endl;
}
return;
}
/*
6 8
1 3
1 2
2 4
3 4
3 5
4 6
4 1
5 6
*/
int main() {
cin >> n >> m;
for(int i=1; i<=m; i++) {
int x,y;
cin >> x >> y;
add(x,y);
}
for(int i=1; i<=n; i++)
if(!dfn[i]) tarjan(i);
//输出连通分量
for(int i=1; i<=cnt; i++) {
for(int j=0; j<scc[i].size(); j++) {
cout << scc[i][j] << " ";
}
cout<<endl;
}
return 0;
}