萌新刚学tarjan , 割点只有76pts
查看原帖
萌新刚学tarjan , 割点只有76pts
113926
typedef楼主2020/8/28 20:02

RT,我把题解代码的这个

int c=0;
for (int i=1;i<=n;i++)
       if (cut[i])
           c++;
printf("%d\n",c);

加入我的代码后成功AC,但是我还是不太明白我的统计方法错在哪里。在我的代码中,我用的是cnt记录割点的个数,但是貌似会出现重复统计。

经仔细检查,代码的其他部分没有错误,可以排除其他部分的干扰,希望大佬帮忙检查。

附我的代码(76分的):

#include<bits/stdc++.h>
using namespace std;
const int SIZE=1e5+10;
int head[SIZE],next[SIZE*2],ver[SIZE*2]
int dfn[SIZE],low[SIZE],stack[SIZE];
int n,m,tot,num,root,cnt;
bool cut[SIZE];
void add(int x,int y){
	ver[++tot]=y,next[tot]=head[x],head[x]=tot;
	return; 
} 
void tarjan(int x){
	dfn[x]=low[x]=++num;
	int flag=0;
	for(int i=head[x];i;i=next[i]){
		int y=ver[i];
		if(!dfn[y]){
			tarjan(y);
			low[x]=min(low[x],low[y]);
			if(low[y]>=dfn[x]){
				flag++;
				if(x!=root||flag>1) cut[x]=1,cnt++;
			} 
		}
		else low[x]=min(low[x],dfn[y]);
	} 
}
int main(){
//	freopen("testin.txt","r",stdin);
//	freopen("testout.txt","w",stdout);
	scanf("%d%d",&n,&m);tot=1;
	for(int i=1;i<=m;i++){
		int x,y;
		scanf("%d%d",&x,&y);
		if(x==y) continue;
		add(x,y),add(y,x);
	} 
	for(int i=1;i<=n;i++){
		if(!dfn[i]){
			root=i;
			tarjan(i);
		}
	}
//	int c=0;//这是题解中的
//	for (int i=1;i<=n;i++)
//        if (cut[i])
//            c++;
	printf("%d\n",cnt);
	for(int i=1;i<=n;i++) if(cut[i]) printf("%d ",i);
	puts("");
	return 0;
}

2020/8/28 20:02
加载中...