无向图割点割边
 
无向图割点割边
算法
边双
点双
  
练习题
P3388 【模板】割点（割顶）
397. 逃不掉的路
364. 网络
395. 冗余路径
P5058 [ZJOI2004]嗅探器
398. 交通实时查询系统
396. 矿场搭建
363. B城
 

 
无向图割点割边
 
割点：无向连通图中，如果删除某点后，图变成不连通，则称该点为割点
 割边：无向连通图中，如果删除某边后，图变成不连通，则称该边为割边
 
边双：边双联通分量ecc：分量中没有割边，每个点属于1个边双
 点双：点双联通分量vcc：分量中没有割点，每条边属于1个点双，割点属于多个点双
 
算法
 
 
顶点 u 是割点只需满足以下两个条件中的其中一个：
 （1）特判树根： u 为树根，且 u 有至少两个子树 。（无向连通图不存在C边，只存在T边和B边，即只存在祖先关系，包括父子关系）
 （2）u 不为树根：在DFS树上u有子节点v，且满足 $dfn[u]\le low[v]$。（意思是说 v 通过 B 边最多只能回到 u）
 
 
边（u，v）是不是割边，当且仅当（u，v）为树边，且满足 $dfn[u]<low[v]$。（意思是说 v 通过 B 边不能回到 u 及其祖先）
 注意：非树边不能是割边，重边不能是割边。构成了一个环，那么就构成一个边双了
 
 
点双和边双都是大环，只不过点双多了一个类型：两个点相连。
 
 
边双
 
找到所有的割边后删去 -> 剩下的就是边双联通分量
边双 + 割边 = 树
两个点必经边数，即树上两点之间的距离
 
建图过程：
 （1） dfs1：找到所有的割边
 （2） dfs2：每个联通块内不通过割边记为同一个ecc
 （3）然后遍历原图所有边
 
点双
 
利用圆方树建图
两点必经点数，即树上距离/2
两边必经点数，即两边所在方点之间必经的点数
 
建图过程：
 
参考链接
 
练习题
 
P3388 【模板】割点（割顶）
 
题意：给出一个 n 个点 m 条边的无向图，求图的割点
 
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn=2e4+10,maxm=1e5+10;

int n,m;
vector<int> e[maxn];
map<int,int> mp[maxn];

int dfn[maxn],low[maxn],times=0;
int iscp[maxn],isce[maxn],fa[maxn],rt;

void dfs(int u)
{
	dfn[u]=low[u]=++times;
	for(auto v: e[u])
	{
		if(!dfn[v])
		{
			fa[v]=u;
			dfs(v);
			low[u]=min(low[u],low[v]);
			if(dfn[u]<low[v]&&mp[u][v]<=1&&mp[v][u]<=1) isce[v]=1;
			if(dfn[u]<=low[v]&&u!=rt) iscp[u]=1;
		}
		else if(v!=fa[u]) low[u]=min(low[u],dfn[v]);
	}
}

int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;++i)
	{
		int u,v;
		scanf("%d%d",&u,&v);
		e[u].push_back(v);
		e[v].push_back(u);
		if(u>v) swap(u,v);
		mp[u][v]++;
	}
	//特判根 
	for(int i=1;i<=n;++i)
	{
		if(!dfn[i])
		{
			rt=i;
			dfs(i);
			int cnt=0;
			for(auto v: e[rt])
				if(fa[v]==rt) ++cnt;
			iscp[rt]=(cnt>1);
		}
	}
	int ans=0;
	for(int i=1;i<=n;++i)
		if(iscp[i]) ans++;
	printf("%d\n",ans);
	for(int i=1;i<=n;++i)
		if(iscp[i]) printf("%d ",i);
	puts("");
	return 0;
}
 
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn=2e4+10,maxm=1e5+10;

int n,m;
vector<int> e[maxn];
map<int,int> mp[maxn];

int dfn[maxn],low[maxn],times=0;
int iscp[maxn],isce[maxn],fa[maxn],rt;

void dfs(int u)
{
	dfn[u]=low[u]=++times;
	int cnt=0;
	for(auto v: e[u])
	{
		if(!dfn[v])
		{
			fa[v]=u;
			dfs(v);
			low[u]=min(low[u],low[v]);
			if(dfn[u]<low[v]&&mp[u][v]<=1&&mp[v][u]<=1) isce[v]=1;
			if(dfn[u]<=low[v])
			{
				cnt++;
				if(u!=rt||cnt>1) iscp[u]=1;
			}
		}
		else if(v!=fa[u]) low[u]=min(low[u],dfn[v]);
	}
}

int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;++i)
	{
		int u,v;
		scanf("%d%d",&u,&v);
		e[u].push_back(v);
		e[v].push_back(u);
		if(u>v) swap(u,v);
		mp[u][v]++;
	}
	for(int i=1;i<=n;++i)
		if(!dfn[i]) rt=i,dfs(i);
	int ans=0;
	for(int i=1;i<=n;++i)
		if(iscp[i]) ans++;
	printf("%d\n",ans);
	for(int i=1;i<=n;++i)
		if(iscp[i]) printf("%d ",i);
	puts("");
	return 0;
}
 
397. 逃不掉的路
 
题意：给定一个无自环、无重边的无向连通图。询问 $(u,v)$ 之间有多少座桥，询问 q 次
 思路：边双缩点后变成一棵树，每一条边就是一座桥，然后就是询问 $(u,v)$ 之间边的数量，直接 lca 即可。
 
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn=1e5+10;

int n,m,q;
vector<int> e[maxn],e2[maxn];

int dfn[maxn],low[maxn],times=0;
int fa2[maxn],isce[maxn];

void dfs1(int u)
{
	dfn[u]=low[u]=++times;
	for(auto v: e[u])
	{
		if(!dfn[v])
		{
			fa2[v]=u;
			dfs1(v);
			low[u]=min(low[u],low[v]);
			if(dfn[u]<low[v]) isce[v]=1;
		}
		else if(v!=fa2[u]) low[u]=min(low[u],dfn[v]);
	}
}
int ecc[maxn],ecnt=0;
void dfs2(int u)
{
	ecc[u]=ecnt;
	for(auto v: e[u])
	{
		if(ecc[v]||fa2[v]==u&&isce[v]||v==fa2[u]&&isce[u]) continue;
		dfs2(v);
	}
}
int fa[maxn][21],depth[maxn];
void dfs3(int u,int f=0)
{
	fa[u][0]=f;
	for(int i=1;i<=20;++i)
		fa[u][i]=fa[fa[u][i-1]][i-1];
	for(auto v: e2[u])
	{
		if(v==f) continue;
		depth[v]=depth[u]+1;
		dfs3(v,u);
	}
}
int lca(int u,int v)
{
	if(depth[u]>depth[v]) swap(u,v);
	int dis=depth[v]-depth[u];
	for(int i=0;(1<<i)<=dis;++i)
		if(dis>>i&1) v=fa[v][i];
	if(u==v) return v;
	for(int i=20;i>=0;--i)
		if(fa[u][i]!=fa[v][i])
			u=fa[u][i],v=fa[v][i];
	return fa[u][0];
}
int getdis(int u,int v)
{
	return depth[u]+depth[v]-2*depth[lca(u,v)];
}
int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;++i)
	{
		int u,v;
		scanf("%d%d",&u,&v);
		e[u].push_back(v);
		e[v].push_back(u);
	}
	dfs1(1);
	
	for(int i=1;i<=n;++i)
		if(!ecc[i]) ecnt++,dfs2(i);
	
	for(int u=1;u<=n;++u)
		for(auto v: e[u])
			if(ecc[v]!=ecc[u])
				e2[ecc[u]].push_back(ecc[v]);
	dfs3(1);
	scanf("%d",&q);
	while(q--)
	{
		int u,v;
		scanf("%d%d",&u,&v);
		printf("%d\n",getdis(ecc[u],ecc[v]));
	}
	return 0;
}
 
364. 网络
 
链接：https://www.acwing.com/problem/content/description/366/
 
题意：给定一张N个点M条边的无向连通图，然后执行Q次操作，每次向图中添加一条边，并且询问当前无向图中“桥”的数量
 
思路：
 
首先用边双缩点成树。
每次加边时，（u，v）路径的桥就不存在了，因此暴力修改 （u，v）路径上的割边
可以用并查集来加速修改，把（u，v）路径上的所有点的 fa 都设为 lca ( u , v ) 这样路径上就可以加速了
 
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn=1e5+10;

int n,m,ans;
vector<int> e[maxn];
map<int,int> mp[maxn];
int dfn[maxn],low[maxn],times;
int isce[maxn];
int depth[maxn],fa[maxn];

void dfs(int u)
{
	dfn[u]=low[u]=++times;
	for(auto v: e[u])
	{
		if(!dfn[v])
		{
			fa[v]=u;
			depth[v]=depth[u]+1;
			dfs(v);
			low[u]=min(low[u],low[v]);
			if(dfn[u]<low[v]&&mp[u][v]<=1&&mp[v][u]<=1) ans++,isce[v]=1;
		}
		else if(v!=fa[u]) low[u]=min(low[u],dfn[v]);
	}
}

void lca(int u,int v)
{
	vector<int> vec;
	if(depth[u]<depth[v]) swap(u,v);
	while(depth[u]>depth[v])
	{
		if(isce[u]) ans--,isce[u]=0;
		vec.push_back(u);		
		u=fa[u];	
	}
	while(u!=v)
	{
		if(isce[u]) ans--,isce[u]=0;
		if(isce[v]) ans--,isce[v]=0;
		vec.push_back(u);
		vec.push_back(v);
		u=fa[u],v=fa[v];
	}
	for(auto x: vec) fa[x]=u;
}

int main()
{
    int Case=0;
	while(scanf("%d%d",&n,&m)&&(n||m))
	{
		times=ans=0;	
		for(int i=1;i<=n;++i)
		{
			dfn[i]=low[i]=depth[i]=fa[i]=isce[i]=0;
			e[i].clear();
			mp[i].clear();
		}
			
		for(int i=1;i<=m;++i)
		{
			int u,v;
			scanf("%d%d",&u,&v);
			e[u].push_back(v);
			e[v].push_back(u);
			if(u>v) swap(u,v);
			mp[u][v]++;
		}
		fa[1]=1;		
		dfs(1);
		
		printf("Case %d:\n",++Case);
		int q,u,v;
		scanf("%d",&q);
		while(q--)
		{
			scanf("%d%d",&u,&v);
			lca(u,v);
			printf("%d\n",ans);
		}	
		printf("\n");
	}	
	return 0;
}
 
395. 冗余路径
 
链接：https://www.acwing.com/problem/content/397/
 
题意：一个图，增加多少条边，使得能成为一个边双连通图。
 
思路：边双缩点，ans = ceil(叶子数量/2)
 
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn=5000+10;

int n,m; 
vector<int> e[maxn];
map<int,int> mp[maxn];
int dfn[maxn],low[maxn],times=0;
int fa[maxn],isce[maxn];

void dfs1(int u)
{
	dfn[u]=low[u]=++times;
	for(auto v: e[u])
	{
		if(!dfn[v])
		{
			fa[v]=u;
			dfs1(v);
			low[u]=min(low[u],low[v]);
			if(dfn[u]<low[v]&&mp[u][v]<=1&&mp[v][u]<=1) isce[v]=1;
		}
		else if(v!=fa[u]) low[u]=min(low[u],dfn[v]);
	}
}
int ecc[maxn],ecnt=0;
void dfs2(int u)
{
	ecc[u]=ecnt;
	for(auto v: e[u])
	{
		if(ecc[v]||v==fa[u]&&isce[u]||u==fa[v]&&isce[v]) continue;
		dfs2(v);
	}
}
int in[maxn];
int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;++i)
	{
		int u,v;
		scanf("%d%d",&u,&v);
		e[u].push_back(v);
		e[v].push_back(u);
		if(u>v) swap(u,v);
		mp[u][v]++;
	}
	for(int i=1;i<=n;++i)
		if(!dfn[i]) dfs1(i);
	
	for(int i=1;i<=n;++i)
		if(!ecc[i]) ++ecnt,dfs2(i);
	
	for(int u=1;u<=n;++u)
		for(auto v: e[u])
			if(ecc[v]!=ecc[u])
				in[ecc[v]]++;
	int ans=0;
	for(int i=1;i<=ecnt;++i)
		if(in[i]==1) ans++;
	printf("%d\n",(ans+1)/2);
	return 0;
}
 
P5058 [ZJOI2004]嗅探器
 
链接：https://www.luogu.com.cn/problem/P5058
 
题意：给定一个无向图，问从 s 到 t 中必经的下标的最小的点是多少
 
思路：
 
可以以 s 为起点建圆方树，那么就可以判断 s 、t 是否连通。
如果连通，那么就从 s 开始往 t 走记录路径上经过的割点的最小值。
割点判断： u 小于等于 n 且度数大于 1 。
 
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn=2e5+10;

int n,s,t;
vector<int> e[maxn],e2[maxn<<1];

int dfn[maxn],low[maxn],times=0;
int sta[maxn],top=0,fa[maxn];
int vcnt;

void dfs1(int u)
{
	dfn[u]=low[u]=++times;
	sta[++top]=u;
	for(auto v: e[u])
	{
		if(!dfn[v])
		{
			fa[v]=u;
			dfs1(v);
			low[u]=min(low[u],low[v]);
			if(dfn[u]<=low[v]) 
			{
				vcnt++;
				while(1)
				{
					int x=sta[top--];
					e2[vcnt].push_back(x);
					e2[x].push_back(vcnt);
					if(x==v) break;	
				}
				e2[vcnt].push_back(u);
				e2[u].push_back(vcnt);
			}
		}
		else if(v!=fa[u]) low[u]=min(low[u],dfn[v]);
	}
}
//int ans=1e9;
//void dfs2(int u,int fa)
//{
//	if(u==t)
//	{
//		if(ans==1e9) puts("No solution");
//		else printf("%d\n",ans);
//		exit(0);
//	}
//	if(u!=s&&e2[u].size()>1&&u<=n) ans=min(ans,u);
//	for(auto v: e2[u])
//	{
//		if(v==fa) continue;
//		dfs2(v,u);
//	}
//}
void dfs2(int u,int ans,int fa)
{
	if(u==t)
	{
		if(ans==0) puts("No solution");
		else printf("%d\n",ans);
		exit(0);
	}
	if(u!=s&&e2[u].size()>1&&u<=n) 
	{
		if(ans==0) ans=u;
		else ans=min(ans,u);
	}
	for(auto v: e2[u])
	{
		if(v==fa) continue;
		dfs2(v,ans,u);
	}
}

int main()
{
	scanf("%d",&n);
	int u,v;
	while(scanf("%d%d",&u,&v)&&(u||v))
		e[u].push_back(v),e[v].push_back(u);
	scanf("%d%d",&s,&t);
	vcnt=n;
	dfs1(s);
	if(dfn[t]==0)
	{
		puts("No solution");
		return 0;
	}
	dfs2(s,0,0);	 
	return 0;
}
 
398. 交通实时查询系统
 
链接：https://www.acwing.com/problem/content/description/400/
 
题意：给定一个无向图，多次询问一条边到另一条边的必经点
 
思路：需要知道一条边属于哪个点双vcc，dfs时把遍历到的边压栈，找到1个点双（low[v]>=dfn[u]）时，弹栈直到 u->v 这条边。
 
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn=1e5+10,maxm=1e6+10;

int n,m;
vector<pair<int,int> > e[maxn];
vector<int> e2[maxn<<1];

int dfn[maxn],low[maxn],times;
int sta[maxn],top=0,sta2[maxm],top2=0;
int vcnt;
int fa[maxn],fa_id[maxn],vcc[maxm];

void dfs1(int u)
{
	dfn[u]=low[u]=++times;
	sta[++top]=u;
	for(auto x: e[u])
	{
		int v=x.first,id=x.second;
		if(!dfn[v])
		{
			fa[v]=u;
			fa_id[v]=id;
			sta2[++top2]=id;
			dfs1(v);
			low[u]=min(low[u],low[v]);
			if(dfn[u]<=low[v])
			{
				vcnt++;
				while(1)
				{
					int x=sta[top--];
					e2[vcnt].push_back(x);
					e2[x].push_back(vcnt);
					if(x==v) break;
				}
				e2[vcnt].push_back(u);
				e2[u].push_back(vcnt);
				while(1)
				{
					int eid=sta2[top2--];
					vcc[eid]=vcnt;
					if(eid==fa_id[v]) break;
				}	
			}
		}
		else if(v!=fa[u])
		{
			low[u]=min(low[u],dfn[v]);
			if(dfn[v]<dfn[u]) sta2[++top2]=id;
		}
	}	
}

int fa2[maxn<<1][21],depth[maxn<<1];
void dfs2(int u,int f=0)
{
	fa2[u][0]=f;
	for(int i=1;i<=20;++i)
		fa2[u][i]=fa2[fa2[u][i-1]][i-1];
	for(auto v: e2[u])
	{
		if(v==f) continue;
		depth[v]=depth[u]+1;
		dfs2(v,u); 
	}
}

int lca(int u,int v)
{
	if(depth[u]<depth[v]) swap(u,v);
	int dis=depth[u]-depth[v];
	for(int i=0;(1<<i)<=dis;++i)
		if(dis>>i&1) u=fa2[u][i];
	if(u==v) return u;
	for(int i=20;i>=0;--i)
	{
		if(fa2[u][i]!=fa2[v][i])
			u=fa2[u][i],v=fa2[v][i];
	}
	return fa2[u][0];
}
int getdis(int u,int v)
{
	return depth[u]+depth[v]-2*depth[lca(u,v)];
}
int main()
{	
	while(scanf("%d%d",&n,&m)&&(n||m))
	{
		for(int i=1;i<=vcnt;++i) e2[i].clear();	
		for(int i=1;i<=n;++i)
		{
			e[i].clear();
			dfn[i]=low[i]=0;
			fa[i]=fa_id[i]=vcc[i]=0;
		}
		times=0;
		top=top2=0;	
		for(int i=1;i<=m;++i)
		{
			int u,v;
			scanf("%d%d",&u,&v);
			e[u].push_back({v,i});
			e[v].push_back({u,i});
		}
		vcnt=n;
		for(int i=1;i<=n;++i)
			if(!dfn[i]) 
			{
				dfs1(i);
				depth[i]=0;
				dfs2(i);
			}
		int q,u,v;
		scanf("%d",&q);
		while(q--)
		{
			scanf("%d%d",&u,&v);
			printf("%d\n",getdis(vcc[u],vcc[v])/2);
		}	
	}
	return 0;
}
 
396. 矿场搭建
 
链接：https://www.acwing.com/problem/content/398/
 链接：https://www.luogu.com.cn/problem/P3225
 
题意：给你一个无向图，你要建立尽量少的救援点，使得图中任意一个点被删除，每个点仍然与一个救援点相连，同时问方案数。
 
思路：建圆方树后对每个点双进行分类讨论：
 
割点数 = 0：需要建2个救援点，方案数 $C_{size}^2$
割点数 = 1：需要建1个救援点，且不能建在割点上，方案数comb(size-1,1)
割点数 > 1：不需建救援点，方案数1
 
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn=1000+10;

int n,m;
vector<int> e[maxn],e2[maxn<<1];

int dfn[maxn],low[maxn],times=0;
int sta[maxn],top=0,fa[maxn],vcnt;
int in[maxn];

void dfs(int u)
{
	dfn[u]=low[u]=++times;
	sta[++top]=u;
	for(auto v: e[u])
	{
		if(!dfn[v])
		{
			fa[v]=u;
			dfs(v);
			low[u]=min(low[u],low[v]);
			if(dfn[u]<=low[v])
			{
				vcnt++;
				while(1)
				{
					int x=sta[top--];
					e2[vcnt].push_back(x);
					e2[x].push_back(vcnt);
					if(x==v) break;
				}
				e2[vcnt].push_back(u);
				e2[u].push_back(vcnt);
			}	
		}
		else if(v!=fa[u]) low[u]=min(low[u],dfn[v]);
	}
}


int main()
{
	int Case=0;
	while(scanf("%d",&m)&&m)
	{
		for(int i=1;i<=vcnt;++i) e2[i].clear();
		for(int i=1;i<=n;++i)
			dfn[i]=low[i]=fa[i]=in[i]=0,e[i].clear();
		top=times=0;
		n=1;
		for(int i=1;i<=m;++i)
		{
			int u,v;
			scanf("%d%d",&u,&v);
			n=max({n,u,v});
			e[u].push_back(v);
			e[v].push_back(u);
			in[u]++,in[v]++;
		}
		vcnt=n;
		for(int i=1;i<=n;++i)
			if(!dfn[i]) dfs(i);
		
		ll ans1=0,ans2=1;
		for(int i=n+1;i<=vcnt;++i)
		{
			int cnt=0;
			for(auto v: e2[i])
				if(v<=n&&e2[v].size()>=2) cnt++; 
			int sz=e2[i].size();
			if(cnt==0) ans1+=2,ans2*=sz*(sz-1)/2;
			else if(cnt==1) ans1++,ans2*=sz-1;
		}
		for(int i=1;i<=n;++i) if(in[i]==0) ans1++;
		printf("Case %d: %lld %lld\n",++Case,ans1,ans2);	
	}
	return 0;
}
 
363. B城
 
题意：无向图，每次删除一个节点和其他节点的边（不删除这个点），问会有多少个 有序点对(x,y) 之间无法连通。
 
思路：Tarjan求圆方树
 
如果 u 不是一个割点，那么答案就是： $2(n-1)$
如果 u 是一个割点，那么答案就是：${\sum }_{v}size[v]\times (n-size[v])+(-size[u])\times size[u]+n-1$
 
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn=1e5+10;

int n,m;
vector<int> e[maxn];
ll ans[maxn],num[maxn];
int dfn[maxn],low[maxn],times=0;
int fa[maxn],iscp[maxn];
int rt=1;

void dfs(int u)
{
	dfn[u]=low[u]=++times;
	num[u]++;
	int sum=0,cnt=0;
	for(auto v: e[u])
	{
		if(!dfn[v])
		{
			fa[v]=u;
			dfs(v);
			low[u]=min(low[u],low[v]);
			num[u]+=num[v];
			if(dfn[u]<=low[v])
			{
				cnt++;
				ans[u]+=1ll*num[v]*(n-num[v]);
				sum+=num[v];
				if(u!=rt||cnt>1) iscp[u]=1; 
			}
		}
		else if(v!=fa[u]) low[u]=min(low[u],dfn[v]);
	}
	if(iscp[u]) ans[u]+=(1ll*n-sum-1)*(sum+1)+n-1;
	else ans[u]=2ll*(n-1);
}

int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;++i)
	{
		int u,v;
		scanf("%d%d",&u,&v);
		e[u].push_back(v);
		e[v].push_back(u); 
	}
	dfs(1);
	for(int i=1;i<=n;++i)
		printf("%lld\n",ans[i]);
	return 0;
}

这东西学了又忘我是真的没救了.. 明明省选前才学的啊
 
这种东西都很套路的拿到搜索树中去看
 
如果一个点子树内没有边能到达这个点及其以上的节点
 
那么这个点就是割点
 
当然也要考虑这个点是根的情况 判定条件为子树大于2
 
板子题
 
#include<bits/stdc++.h>

using namespace std;

int read() {
    int _ = 0, ___ = 1; char __ = getchar();
    for(; !isdigit(__); __ = getchar()) if(__ == '-') ___ = -1;
    for(; isdigit(__); __ = getchar()) _ = (_ << 3) + (_ << 1) + (__ ^ 48);
    return _ * ___;
}

const int N = 1e6 + 10;

int to[N << 1], head[N], nxt[N], e;
int n, m, dfn[N], low[N];;
int vis[N], cnt, tot;

void add(int x, int y, bool k = 1) {
    to[++ e] = y; nxt[e] = head[x]; head[x] = e;
    if(k) add(y, x, 0);
}

void dfs(int x, int root, int fa) {
    int sz = 0;
    dfn[x] = low[x] = ++ cnt;
    for(int i = head[x]; i; i = nxt[i]) {
        ++ sz;
        if(!dfn[to[i]]) {
            dfs(to[i], 0, x);
            low[x] = min(low[x], low[to[i]]);
            if(root && sz >= 2 && !vis[x]) 
                vis[x] = ++ tot;
            if(!root && low[to[i]] >= dfn[x] && !vis[x]) 
                vis[x] = ++ tot;
        }
        else if(to[i] != fa)
            low[x] = min(low[x], dfn[to[i]]);
    }
}

int main() {
#ifndef ONLINE_JUDGE
    freopen("3388.in", "r", stdin);
    freopen("3388.out", "w", stdout);
#endif
    n = read(), m = read();
    for(int i = 1; i <= m; ++ i)    
        add(read(), read());
    for(int i = 1; i <= n; ++ i) 
        if(!dfn[i])
            dfs(i, 1, 0);
    printf("%d\n", tot);
    for(int i = 1; i <= n; ++ i)
        if(vis[i]) 
            printf("%d ", i);
    return 0;
}

 
文章目录
 
无向图的割点及判定
对搜索起点的处理
对重边的处理
参考实现
 

 
Tarjan算法的核心思想已经在《Tarjan求无向图割边》中介绍了，不清楚的读者可以先行阅读那部分内容，这里直接从介绍割点开始。
 
无向图的割点及判定
 
对于无向连通图$G(V,E)$，若删去点$v\in V$及其邻边
    
     
      
       
        ∀
       
       
        u
       
       
        ∈
       
       
        {
       
       
        V
       
       
        −
       
       
        v
       
       
        }
       
       
        ,
       
       
        (
       
       
        v
       
       
        ,
       
       
        u
       
       
        )
       
       
        ∈
       
       
        E
       
      
      
       \forall u\in \{V-v\}, (v,u)\in E
      
     
    ∀u∈{V−v},(v,u)∈E后，$G$被分为两个或更多互不连通的子图，则称$v$为割点或割顶。
 
根据上面$dfn$和$low$，很容易能想出割边的方法——无向边$(u,v)$是割边，当且仅当搜索树上存在$u$的一个子节点$v$，满足：
 
$$dfn[u]\le low[v]$$
 
如果不明白上式，可以参考之前文章中抽象的三种图形。当$dfn[u]=low[v]$时，两条链合起来状似闭环，此时无割边，但两条链$dfn$最小的咬合点显然是割点。
 
特别的，对于我们搜索的起点，上述判定方法还需限定条件，先来看一个反例：
 

 
 
上图中，有唯一满足$dfn[u]\le low[v]$的$(1,2)$，但去掉$1$后，剩余图为：
 

 
 
并没有被分为两个或以上的互不连通子图，所以这里搜索起点$1$尽管满足上面的判别式，但并不是割点。
 
是不是所有的搜索起点都不是割点呢？提出这个问题固然在思考，但细想却很好笑——任意点都能作为搜索起点，如果这句话成立，则任意点都不是割点。
 
对搜索起点的处理
 
如果搜索起点有两个以上的子树，则意味着在搜索树上，根结点出度为二或以上。根据树的性质，如果我们删去根节点及其邻边，则原树将裂解成子树个数个互不连通的树。若不明白，任意找几棵树观察便知。
 
要在代码中实现上述判断，可记录从根节点出发的邻点调用的DFS次数即可，伪代码如下：
 
int children = 0;
for (int v: G[u]) {
    if (!vis[v]) {
        children++;
        dfs(v);
    }
}
if (children >= 2)  u是割点
 
对重边的处理
 
对割点问题而言，删去割点将会将所有相邻的重边删去，所以割点问题并不受重边影响。
 
参考实现
 
//
// Created by Visors on 2020/10/29.
//
// 题目名：P3388 【模板】割点（割顶）
// 题目来源：luogu
// 题目链接：https://www.luogu.com.cn/problem/P3388
// 算法：Tarjan
// 用途：无向图割点
// 时间复杂度：O(n+m)
//

#include <bits/stdc++.h>

using namespace std;

struct Tarjan {
    struct Edge {
        int to, next;

        Edge() = default;

        Edge(int to, int next) : to(to), next(next) {}
    };

    int vertexNum{}, edgeNum{};
    int cnt{};              // 当前时间戳
    int root{};             // 保存当前搜索树根
    vector<Edge> edges;
    vector<int> heads;
    vector<int> dfn;        // 时间戳
    vector<int> low;        // 最早追溯时间
    set<int> cuts;          // 割点编号集

    void init(int n, int m) {
        cnt = 0;
        vertexNum = n;
        edgeNum = m;
        heads.resize(vertexNum);
        fill(heads.begin(), heads.end(), -1);
        dfn.resize(vertexNum);
        low.resize(vertexNum);
        cuts.clear();
    }

    void addEdge(int u, int v) {
        edges.emplace_back(v, heads[u]);
        heads[u] = edges.size() - 1;
    }

    void dfs(int u) {
        dfn[u] = low[u] = ++cnt;
        int tot = 0;
        for (int i = heads[u]; ~i; i = edges[i].next) {
            int &v = edges[i].to;
            if (!dfn[v]) {
                dfs(v);
                low[u] = min(low[u], low[v]);
                if (low[v] >= dfn[u]) {
                    tot++;
                    if (u != root || tot > 1) cuts.insert(u);   // 对树根特判
                }
            } else low[u] = min(low[u], dfn[v]);
        }
    }

    void run() {
        for (int i = 0; i < vertexNum; i++)
            if (!dfn[i]) {
                root = i;
                dfs(i);
            }
    }
} tarjan;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr), cout.tie(nullptr);
    int n, m;
    cin >> n >> m;
    tarjan.init(n, m);
    for (int i = 1, u, v; i <= m; i++) {
        cin >> u >> v;
        if (u == v) continue;
        u--, v--;
        tarjan.addEdge(u, v);
        tarjan.addEdge(v, u);
    }
    tarjan.run();
    cout << tarjan.cuts.size() << endl;
    bool first = true;
    for (int it:tarjan.cuts)
        if (first) {
            cout << it + 1;
            first = false;
        } else cout << ' ' << it + 1;
    cout << endl;
    return 0;
}

无向图中割点：去掉这个点连通分量增加。
 
求法：当一个点为树根时，如果他的儿子数量大于一则这个点为割点，(一棵树的根节点有数量大于一的儿子那么去掉树根，这棵树不连通)
 
当这个点u的dfn[u]<=low[v]  (v是他能到的点)这个点为割点，因为当满足dfn[u]<=low[v]时v无法达u之前的点，那么去掉u这个点后连通分量必然增加如图
 
        很明显可以看出图二去掉u点连通分量没有增加，为图一去掉u点连通分量增加
 
 
无向图的桥：当去掉某条边图的连通分量增加则称为此边为桥。
 
求法：当碰到一个点u时dfn[u]<low[v]  (v是能通过u到达的点) 那么u到v这条边是一个桥，可以参考上面那两张图。