【模板】割点（割顶）

题目背景

割点

题目描述

给出一个 \(n\) 个点，\(m\) 条边的无向图，求图的割点。

输入格式

第一行输入两个正整数 \(n,m\)。

下面 \(m\) 行每行输入两个正整数 \(x,y\) 表示 \(x\) 到 \(y\) 有一条边。

输出格式

第一行输出割点个数。

第二行按照节点编号从小到大输出节点，用空格隔开。

样例 #1

样例输入 #1

6 7
1 2
1 3
1 4
2 5
3 5
4 5
5 6

样例输出 #1

1 
5

提示

对于全部数据，\(1\leq n \le 2\times 10^4\)，\(1\leq m \le 1 \times 10^5\)。

点的编号均大于 \(0\) 小于等于 \(n\)。

tarjan图不一定联通。

解题思路：

割点模板题

Code：

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+5;
int tot,h[maxn],nex[maxn<<1],to[maxn<<1];
inline void add(int a,int b) {
	nex[++tot]=h[a],h[a]=tot,to[tot]=b;
	nex[++tot]=h[b],h[b]=tot,to[tot]=a;
}
int dfn[maxn],low[maxn],cnt,flag[maxn];
int n,m,rt,ans;
inline void dfs(int u,int fa) {
	low[u]=dfn[u]=++cnt;
	int x=0;
	for(int i=h[u];i;i=nex[i]) {
		int v=to[i];
		if(v==fa) continue;
		if(!dfn[v]) {
			x++;
			dfs(v,u);
			low[u]=min(low[v],low[u]);
			if(low[v]>=dfn[u]) {
				if(u!=rt) flag[u]++;
				if(u==rt&&x==2) flag[u]++;
			}
		}
		else low[u]=min(dfn[v],low[u]);
	}
}
int main() {
	cin>>n>>m;
	for(int i=1,a,b;i<=m;i++) {
		cin>>a>>b;
		add(a,b);
	}
	for(int i=1;i<=n;i++) if(!dfn[i]) rt=i,dfs(i,0);
	for(int i=1;i<=n;i++) if(flag[i]>0) ans++;
	cout<<ans<<'\n';
	for(int i=1;i<=n;i++) if(flag[i]>0) cout<<i<<' ';
}