- 2022tysc1451 的博客
强联通分量
- 2025-8-19 9:21:06 @
void tarjan(int u){
d[u]=low[u]=++cnt;
flag[u]=true;//标记是否在栈中
s.push(u);
for(int i=0;i<g[u].size();i++){
int v=g[u][i];
if(d[v]==-1){
tarjan(v);
low[u]=min(low[u],low[v]);
}else if(flag[v])low[u]=min(low[u],d[v]);
}
if(d[u]==low[u]){//截断的位置
int v,sum=0;
t++;//强连通分量的编号
do{
v=s.top();
s.pop();
flag[v]=false;
f[v]=t;
sum++;
}while(u!=v);
if(sum>1)ans++;
}
}