强连通分量
我们首先定义两种边:返祖边为从一个点指向其祖先的边;横叉边从某个点指向树中另一个子树中的点的边。两者统称为非树边。而剩下的边即为树边,树边也就是在 \(dfs\) 树上的边。
我们定义 \(dfn_i\) 为 \(i\) 是第几个被 \(dfs\) 到的,\(low_i\) 从 \(i\) 出发走任意条边,但是最后一条边必须是返祖边的情况下能够到达的点的 \(dfn\) 的最小值。
于是我们便有了求出 \(dfn\) 和 \(low\) 的代码:
void tar(int u){
low[u]=dfn[u]=++tot;
stk[++top]=u;
ist[u]=1;
for(int i=h[u];~i;i=ne[i]){
int j=e[i];
if(!dfn[j]){
tar(j);
low[u]=min(low[u],low[j]);
}
else if(ist[j]){
low[u]=min(low[u],dfn[j]);
}
}
}
接着我们考虑怎么通过 \(low\) 和 \(dfn\) 求出强连通分量。
我们假设现在遇到了一个点 \(x\),并且 \(dfn_x=low_x\)。这说明从 \(x\) 出发按照之前的要求能走到的 \(dfn\) 最小的点是他自己。
换句话说,\(x\) 是其所在强连通分量的最上面的点。
于是我们不断弹出栈,直到弹出了 \(x\)(不难证明 \(x\) 在栈中),弹出的这些点与 \(x\) 同属一个强连通分量,于是就做完了。
完整代码:
#include<bits/stdc++.h>
#define int long long
#define N 10005
#define M 100005
using namespace std;
int n,m,h[N],e[M],ne[M],idx,cnt,tot;
int stk[N],col[N],dfn[N],low[N],top;
bool ist[N],st[N];
vector<int>res[N];
void add(int a,int b){
e[idx]=b;ne[idx]=h[a];h[a]=idx++;
}
void tar(int u){
low[u]=dfn[u]=++tot;
stk[++top]=u;
ist[u]=1;
for(int i=h[u];~i;i=ne[i]){
int j=e[i];
if(!dfn[j]){
tar(j);
low[u]=min(low[u],low[j]);
}
else if(ist[j]){
low[u]=min(low[u],dfn[j]);
}
}
if(dfn[u]==low[u]){
cnt++;
int y;
do{
y=stk[top--];
ist[y]=0;
col[y]=cnt;
res[cnt].push_back(y);
}while(y!=u);
}
}
signed main(){
cin>>n>>m;
memset(h,-1,sizeof h);
for(int i=1;i<=m;i++){
int a,b;
cin>>a>>b;
add(a,b);
}
for(int i=1;i<=n;i++){
if(!dfn[i]){
tar(i);
}
}
cout<<cnt<<'\n';
for(int i=1;i<=n;i++){
if(!st[col[i]]){
sort(res[col[i]].begin(),res[col[i]].end());
for(auto it:res[col[i]]){
cout<<it<<' ';
}
cout<<'\n';
st[col[i]]=1;
}
}
return 0;
}
标签:cnt,有向图,连通性,未完结,int,ist,++,dfn,low
From: https://www.cnblogs.com/zxh923aoao/p/18411566