P3388 【模板】割点（割顶）

可口深度优先生成树求调

#include<bits/stdc++.h>
using namespace std;
const int N=2e4+5;
int n,m;
vector<int>G[N];
int dfn[N],low[N],ans,idx;
bool iscut[N];
void dfs(int u,int fa)
{
	dfn[u]=low[u]=++idx;
	int cd=0;
	for(int i=0; i<G[u].size(); i++)
	{
		int v=G[u][i];
		if(!dfn[v])
		{
			cd++;
			dfs(v,u);
			low[u]=min(low[u],low[v]);
			if(low[v]>=dfn[u]&&u!=1)iscut[u]=1;
		}
		else if(dfn[v]<dfn[u]&&v!=fa)low[u]=min(low[u],dfn[v]);
	}
	if(u==1&&cd>=2)iscut[1]=1;
}
signed main(){
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	cin>>n>>m;
	for(int i=1; i<=m; i++)
	{
		int x,y;
		cin>>x>>y;
		G[x].push_back(y);
		G[y].push_back(x);
	}
	dfs(1,1);
	for(int i=1; i<=n; i++)
		ans+=iscut[i];
	cout<<ans<<'\n';
	for(int i=1; i<=n; i++)
		if(iscut[i])cout<<i<<' ';
    return 0;
}

悬棺