关于此题的特判
查看原帖
关于此题的特判
81708
lion0514楼主2021/6/19 18:15

众所周知大部分人的程序里都有一句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;
}
2021/6/19 18:15
加载中...