连通性问题大杂烩

zcxnb / 2024-10-13 / 原文

前言

连通性问题确实时一大比较难啃得蛋糕，每次都要先学习一遍，还不如一次学到通

无向图的连通性问题

求割点

连通图：连通图内的所有点都可以互相到达
割点：将割点删掉后整张图不连通

定理1：

一个点s是割点，当且仅当s作为该连通图的根时，会把连通图分为不相连的几部分

定理2：

一个非根节点u是割点，当且仅当u存在一个子节点v不存在一条边连向u的祖先

一开始我认为只要存在一条边连向祖先就不算割点，但这里举出反例：

实现

考虑dfs序，就是将节点编号为dfs遍历到的顺序
我们设一个dfn表示dfs序，设low表示当前节点能回到的最大祖先的编号，只要存在子节点v的$low[v]>=dfn[u]$ 就可以了

代码

#include<bits/stdc++.h>
#define pii pair<int,int>
using namespace std;
const int N=2e5+5;
int n,m,u,v,tot,ans;
int dfn[N],low[N],vis[N],dot[N];
vector<pii>b[N];
void dfs(int x,int nxt){
	dfn[x]=low[x]=++tot;
	vis[x]=1;
	bool cnt=0;
	int num=0;
	for(auto i:b[x]){
		if(nxt==i.second)  continue;//这里大抵是没有用的
		int k=i.first;//要开局部变量，不要像我一样手懒开全局变量寄掉
		if(!vis[k]){
			num++;
			dfs(k,i.second);
			low[x]=min(low[x],low[k]);
			if(low[k]>=dfn[x])  cnt=1;
		}
		else{
			low[x]=min(low[x],dfn[k]);//无向图中也可以写low
		}
	}
	if(!nxt){
		if(num>1)  dot[++ans]=x;//注意特判根节点的情况
	}
	else if(cnt){
		dot[++ans]=x;
	}  
}
int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++){
		scanf("%d%d",&u,&v);
		b[u].push_back({v,i});
		b[v].push_back({u,i});
	}
	for(int i=1;i<=n;i++){
		if(!vis[i]){
			dfs(i,0);
		}
	}
	sort(dot+1,dot+ans+1);
	printf("%d\n",ans);
	for(int i=1;i<=ans;i++){
		printf("%d ",dot[i]);
	}
}```
###割边
只需要把 $low[v]>=dfn[u]$ 改成 $low[v]>dfn[u]$ 就行了，因为u的所有后代都到达不了v，从u->v的边一定是割边