强连通分量
title: 强连通分量
categories:
- ICPC
tags:
- null
abbrlink: 4b4a3d7
date: 2023-02-10 00:00:00
#scc:极大的强连通子图(两两相互可达)
const int N=10010;
int n,m,a,b;
vector<int> e[N];
int dfn[N],low[N],tot;
int stk[N],instk[N],top;
int scc[N],siz[N],cnt;
void tarjan(int x){
//入x时,盖戳、入栈
dfn[x]=low[x]=++tot;
stk[++top]=x,instk[x]=1;
for(int y : e[x]){
if(!dfn[y]){//若y尚未访问
tarjan(y);
low[x]=min(low[x],low[y]);//回x时更新low
}
else if(instk[y])//若y已访问且在栈中
low[x]=min(low[x],dfn[y]);//在x时更新low
}
//离x时,收集SCC
if(dfn[x]==low[x]){//若x是SCC的根
int y; ++cnt;
do{
y=stk[top--];
instk[y]=0;
scc[y]=cnt;//SCC编号
++siz[cnt];//SCC大小
}while(y!=x);
}
}
int main(){
cin>>n>>m;
while(m--)
cin>>a>>b, e[a].push_back(b);
for(int i=1; i<=n; i++)//可能不连通
if(!dfn[i]) tarjan(i);
int ans=0;
for(int i=1;i<=cnt;i++)
if(siz[i]>1) ans++;//输出的是两个点以上的scc
cout<<ans<<endl;
return 0;
}
本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来源 爱飞鱼的blog!