题目背景
割点
题目描述
给出一个n个点，m条边的无向图，求图的割点。
输入输出格式
输入格式：
第一行输入n,m
下面m行每行输入x,y表示x到y有一条边
输出格式：
第一行输出割点个数
第二行按照节点编号从小到大输出节点，用空格隔开
输入输出样例
输入样例#1：
6 7
1 2
1 3
1 4
2 5
3 5
4 5
5 6
输出样例#1：
1
5
说明
对于全部数据，n≤20000，m≤100000
点的编号均大于0小于等于n。
tarjan图不一定联通。
#include<cmath>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
long long read()
{
long long x=,f=;
char ch=getchar();
while(ch>''||ch<'')
{
if(ch=='-')
f=-;
ch=getchar();
}
while(ch>=''&&ch<='')
{
x=x*+ch-'';
ch=getchar();
}
return x*f;
}
const int maxn=;
int n,m,num,cnt,ans;
int fa[maxn],low[maxn],head[maxn],dfn[maxn];
struct edge
{
int u,v,nxt;
} e[maxn<<];
bool cut[maxn];
inline void add(int u,int v)
{
e[++num].u=u;
e[num].v=v;
e[num].nxt=head[u];
head[u]=num;
}
void tarjan(int x)
{
int in=;
dfn[x]=low[x]=++cnt;
for(int v,i=head[x]; i; i=e[i].nxt)
{
v=e[i].v;
if(!dfn[v])
{
fa[v]=fa[x];
tarjan(v);
low[x]=fmin(low[x],low[v]);
if(low[v]>=dfn[x]&&x!=fa[x])
cut[x]=true;
if(x==fa[x])
++in;
}
low[x]=fmin(low[x],dfn[v]);
}
if(x==fa[x]&&in>=)
cut[fa[x]]=true;
}
int main()
{
n=read(),m=read();
for(int i=; i<=n; ++i)
fa[i]=i;
for(int i=; i<=m; ++i)
{
int u,v;
u=read(),v=read();
add(u,v);
add(v,u);
}
for(int i=; i<=n; ++i)
if(!dfn[i])
tarjan(i);
for(int i=; i<=n; ++i)
if(cut[i])
++ans;
printf("%d\n",ans);
for(int i=; i<=n; ++i)
if(cut[i])
printf("%d ",i);
return ;
}