求助!割点重复计算?
查看原帖
求助!割点重复计算?
716721
leo12334楼主2024/9/23 09:01

求助各位大佬,我想在求割点的时候直接记录割点数量,结果只得了76,在测试点4WA了,割点都求对了,但计数时应该是325个,我输出了335个,想问下问题出在哪里QAQ 这是错误的代码,ans记录割点数量:

void dfs(int root,int x,int fa){
	dfn[x]=low[x]=++tt;
	int ch=0; 
	for(int i=head[x];i;i=e[i].next){
		int y=e[i].to;
		if(!dfn[y]){
			ch++;
			dfs(root,y,x);
			low[x]=min(low[x],low[y]);
			if(dfn[x]<=low[y]&&x!=root)iscut[x]=1,ans++;
		}
		else low[x]=min(low[x],dfn[y]);
	}
	if(x==root&&ch>=2)iscut[x]=1,ans++; 
}

而把ans++删掉,改为dfs之后从头到尾统计一遍,再输出,就是对的了,有谁知道问题出在哪吗

	for(int i=1;i<=n;i++)if(iscut[i])ans++;
	cout<<ans<<endl;
2024/9/23 09:01
加载中...