#11有误
估计是根节点的割点判断有误
但是将注释部分写进代码则会0分,不知道哪来的2号割点
没有用栈之类的方法,代码从割边改编而来
#include<bits/stdc++.h>
#define _for(i,a,b) for(int i=a;i<=b;i++)
#define __for(i,a,b) for(int i=a;i>=b;i--)
typedef unsigned long long ull;
using namespace std;
const int maxn=2e4,maxm=1e5;
struct Edge{
int u, v, w;//起点,终点,权值
int nxt = -1;
}
edge[2*maxm + 10];
int head[maxn + 10], cnt = 0;
void init()//初始化链式前向星
{
cnt=0;
memset(head, -1, sizeof(head));
return ;
}
void add_edge(int frm, int to, int val)
{
edge[++cnt].u = frm;
edge[cnt].v = to;
edge[cnt].w = val;
edge[cnt].nxt = head[frm];
head[frm] = cnt;
return ;
}
int res=0;
int dfn[maxn+10],low[maxn+10];
int num=0;
bool cut[maxn+10];
void tarjan(int x,int fa){
dfn[x]=low[x]=++num;
if(fa==-1&&head[x]==-1){
cut[x]=1,res++;
}
for(int i=head[x];~i;i=edge[i].nxt){
int y=edge[i].v;
if(!dfn[y]){
tarjan(y,x);
low[x]=min(low[x],low[y]);
if(dfn[x]<=low[y])
if(!cut[x])//防止重复
cut[x]=1,res++;
}
else if(edge[i].v!=fa){
low[x]=min(low[x],dfn[y]);
}
}
return;
}
int n,m;
int main(){
init();
memset(cut,0,sizeof cut);
memset(dfn,0,sizeof dfn);
memset(low,0,sizeof low);
scanf("%d%d",&n,&m);
_for(i,1,m){
int frm,to;
scanf("%d%d",&frm,&to);
add_edge(frm,to,1);add_edge(to,frm,1);
}
_for(i,1,n)if(!dfn[i]){
tarjan(i,-1);
cut[i]=0,res--;//特别地:非孤独根节点不是割点
// //除非有两个相邻的y,使得dfn[rot]<=low[y];
// int tot=0;
// for(int j=head[i];~j;j=edge[j].nxt)if(dfn[i]<=low[edge[j].v])tot++;
// if(tot>=2)cut[i]=1,res++;
}
printf("%d\n",res);
_for(i,1,n) if(cut[i])printf("%d ",i);
puts("");
fclose(stdin);
return 0;
}