Tarjan有向图的强连通分量模板
作者:
风城玫瑰.01
,
2023-11-28 22:10:12
,
所有人可见
,
阅读 88
#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 1e4 + 10 , M = 1e5 + 10;//N为点数,M为边数
int n,m;//n个点,m条边
int h[N],e[M],ne[M],idx;//存图
int dfn[N],low[N],ts;//时间戳dfn[x]表示x点第一次被访问的顺序,追溯值low[x]表示从x点出发,能够访问到的最早时间戳
int stk[N],in_stk[N],top;//stk[]数组模拟栈,in_stk[]标志某点是否在栈中
int scc[N],sizes[N],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] = ++ ts;
stk[++ top] = x , in_stk[x] = 1;
for( int i = h[x] ; ~i ; i = ne[i] )
{
int j = e[i];
if(!dfn[j])
{
Tarjan(j);
low[x] = min(low[x] , low[j]);
}
else if(in_stk[j]) low[x] = min(low[x] , dfn[j]);
}
if(low[x] == dfn[x])
{
int y; ++ cnt;
do{
y = stk[top --] , in_stk[y] = 0;
scc[y] = cnt;
++ sizes[cnt];
}while(y != x);
}
}