众所周知大部分人的程序里都有一句if(点是根&&孩子>1)则标记为割点
然而根的dfn显然是1,任何点的dfn都不可能小于它,所以应该可以在if(lw[y]>=dfn[x])
的地方被踢掉
所以根到底有没有需要去特判?
附代码,64分,求助
#include<bits/stdc++.h>
using namespace std;
struct road{
int next,to;
}r[500000];int hd[500000],cnt;
void insert(int frm,int to){
r[++cnt]=(road){hd[frm],to};
hd[frm]=cnt;
}
int n,m,nm=0,dfn[100000],lw[100000];
long long ans[100000];
int tarjan(int x,int fa){
dfn[x]=lw[x]=++nm;
int cnt=1;
map<int,bool> bk;
for(int y,i=hd[x];i;i=r[i].next){
if(!dfn[y=r[i].to]){
int num=tarjan(y,x);
if(!bk[lw[y]]){bk[lw[y]]=1;
lw[x]=min(lw[x],lw[y]);
cnt+=num;
if(lw[y]>=dfn[x]||){
ans[x]=1;
// cout<<y<<' '<<num<<':'<<ans[x]<<" ";
}
}
}
else if(y!=fa){
lw[x]=min(lw[x],dfn[y]);
}
}
return cnt;
}
int main(){
cin>>n>>m;
for(int i=1,u,v;i<=m;++i,insert(u,v),insert(v,u)) scanf("%d %d",&u,&v);
for(int i=1;i<=n;++i)
if(!dfn[i])
tarjan(i,0);
int sm=0;
for(int i=1;i<=n;++i) if(ans[i])++sm;
cout<<sm;
for(int i=1;i<=n;++i)if(ans[i])cout<<endl<<i;
return 0;
}