前言
连通性问题确实时一大比较难啃得蛋糕，每次都要先学习一遍，还不如一次学到通
无向图的连通性问题
求割点
连通图：连通图内的所有点都可以互相到达
割点：将割点删掉后整张图不连通
定理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]);}
}```
###
