Description
Fanvree很聪明，解决难题时他总会把问题简单化。例如，他就整天喜欢把图转化为树。但是他不会缩环，那他怎么转化呢？ 这是一个有n个点m条双向边的图，Fanvree会选定一个节点，然后删掉这个节点和这个点连出去的边，如果变成了一棵树，那么这个节点便是可行的，什么是树呢？树也即无简单环的无向连通图。告诉Fanvree可能的节点是什么。
Input
第一行两个正整数n和m，表示有n个点m条边，保证n≥2。接下来m行，每行两个整数v,u，表示v和u之间有一条无向边1≤v,u≤n，保证没有重边和自环。
Output
第一行一个正整数ns，表示这个图中有ns个结点可选。接下来一行，共ns个整数，每个整数表示一个可选结点的编号。请按编号从小到大的顺序输出。数据保证图中至少存在一个可选的结点。
Hint
对于40%的数据：n，m<=1000；
另外存在10%的数据：m=n-1；
另外存在20%的数据：m=n；
对于100%的数据：n，m<=100000。
Solution
预处理出割点，统计每个点的度，如果m-这个点的度==n-2并且这个点不是割点，那么它就可以删。
#include<cstring>
#include<cstdio>
#include<iostream>
#include<algorithm>
#define maxn 200005
using namespace std;
struct Edge{
int u;
int v;
int next;
int id;
}edge[maxn];
int first[maxn],last[maxn],low[maxn],dfn[maxn],du[maxn],ans[maxn];
int node,n,m,x,y,dfn_TimeClock,cnt;
bool vis[maxn],cut[maxn];
void addedge(int u,int v,int id){
edge[++node]=(Edge){u,v,0,id};
if(first[u]==0)first[u]=node;
else edge[last[u]].next=node;
last[u]=node;
}
void init(){
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++){
scanf("%d%d",&x,&y);
du[x]++;
du[y]++;
addedge(x,y,i);
addedge(y,x,i);
}
}
void Tarjan_h(int i,int fd){
vis[i]=true;
dfn[i]=low[i]=++dfn_TimeClock;
int xxx=0;
for(int p=first[i];p;p=edge[p].next){
int j=edge[p].v,id=edge[p].id;
if(vis[j]){
if(dfn[j]<dfn[i]&&id!=fd){
low[i]=min(low[i],dfn[j]);
}
continue;
}
xxx++;
Tarjan_h(j,id);
low[i]=min(low[i],low[j]);
if(low[j]>=dfn[i])cut[i]=1;
}
if(xxx==1&&fd==0)cut[i]=0;
}
void workk(){
Tarjan_h(1,0);
for(int i=1;i<=n;i++){
if(m-du[i]==n-2&&!cut[i]){
ans[++cnt]=i;
}
}
}
int main(){
init();
workk();
printf("%d
",cnt);
for(int i=1;i<=cnt;i++){
printf("%d ",ans[i]);
}
printf("
");
return 0;
}