社区讨论
求助,并查集(代码附注释),为什么全是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 条回复,欢迎继续交流。
正在加载回复...