割点模版题
dfn表示深搜次序,low表示该点可以到达的最远距离.无向图存双向边
若为根,有两个及以上孩子算割点,不为根,点u存在连接的一个点v访问的最小值low[v]大于等于(等于就是最后还是走到这个点)dfn[u],则u为割点
//tarjan割点
#include <bits/stdc++.h>
using namespace std;
const int M = 250000;
struct E{int v,nxt;};
E edge[M];
int n,m,head[M],dfn[M],low[M],cnt,bo[M];
int ans;
void tarjan(int u,int fa){
dfn[u] = low[u] = ++cnt;
int child = 0;
for(int v,i=head[u];i;i=edge[i].nxt){
v = edge[i].v;
if(!dfn[v]){
tarjan(v,fa);
low[u] = min(low[u],low[v]);
if(low[v]>=dfn[u]&&u!=fa){
bo[u] = 1;
}
if(u==fa)
child++;
}else low[u] = min(low[u],dfn[v]);
}
if(child>=2)bo[fa]=1;
}
int main()
{
scanf("%d %d",&n,&m);
int ccnt = 0;
for(int i=1;i<=m;i++){
int u,v;
scanf("%d %d",&u,&v);
ccnt++; edge[ccnt].v = v; edge[ccnt].nxt = head[u]; head[u]=ccnt;
ccnt++; edge[ccnt].v = u; edge[ccnt].nxt = head[v]; head[v]=ccnt;
}
for(int i=1;i<=n;i++)
if(!dfn[i])
tarjan(i,i);
for(int i=1;i<=n;i++)if(bo[i])ans++;
printf("%d\n",ans);
for(int i=1;i<=n;i++)
if(bo[i])printf("%d ",i);
return 0;
}