社区讨论

求助,并查集(代码附注释),为什么全是wa

P2307迷宫参与者 1已保存回复 0

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
0 条
当前快照
1 份
快照标识符
@lo2ycaab
此快照首次捕获于
2023/10/23 21:47
2 年前
此快照最后确认于
2023/10/23 21:47
2 年前
查看原帖
C
#include<bits/stdc++.h>
using namespace std;
int pre[10086];//并查集前驱数组 
int book=0;//环路标志位 
int find(int x){
	if(pre[x]==x)
	return x;
	return find(pre[x]);//找祖宗节点 
}
int merge(int x,int y){
	pre[find(x)]=find(y);//合并 
}
int main(){
	for(int i=0;i<10086;i++){
	pre[i]=i;//前驱数组初始化并指向自己 
}

	int x,y;
	while(cin>>x>>y){
		if(x==-1&&y==-1)//当输出双-1时,程序结束 
		return 0;
		else if(x==0&&y==0){//当输出双0时,判断并输出 
		if(book==0)
		cout<<1<<endl;//未出现环路 
		else
		cout<<0<<endl;//出现环路 
		continue;	
		}
		if(find(x)==find(y))//若新节点x,y祖宗一致,则代表x,y已经连通,再次连通则出现环路,与小希想法不符
		book=1;//环路标志位 
		if(find(x)!=find(y))//祖宗不一致,进行连通合并 
		merge(x,y);
	}
	return 0;
}

回复

0 条回复,欢迎继续交流。

正在加载回复...