「金明的乐多赛|并查集」金明写代码
描述
金明跟K在写代码,金明忽然发现,程序好像出了问题,比如:变量ans的值莫名其妙变成了0,x1的值变成了x2.
金明检查了一遍又一遍,可就是不知道,代码哪里错了。K说,我教你写一个代码来判断程序是否错误吧。
接下来就要你来写这个神奇的代码。
金明的程序里面有n个变量间的约束关系,每两个变量间只有相等或不等2种情况,给定一组变量间的关系,请判断是否成立,如果不成立就说明金明的程序里有bug,输出NO不然就输出YES,说明没问题
金明有t份代码,请给这些代码做出判断
輸入
第一行,一个整数t
面共t组数据,每组数据第一行为一个正整数n,下面有n 行,每行三个正整数,i,j,z当z等于1时说明j==i
z等于0时说明两者不相等
輸出
每组数据一行,NO或YES
輸入範例 1
2
2
1 2 1
1 2 0
2
1 2 1
2 1 1
輸出範例 1
NO
YES
提示
1 <= t <= 10
1 <= n <= 100,000
1 <= i, j <= 1,000,000,000
我的代码调试了很久都是PAC,2个AC,7个WA,1个RE
请问各位优秀的OIer,这一题究竟错在哪里?
[昆虫科学院并查集教程1:金明写代码](
#include<iostream>
#include<cstring>
#define int long long
using namespace std;
int s[20000000];
struct two{
int x,y;
}a[1001];
int find(int x){
if(x==s[x])return x;
else{
s[x]=find(s[x]);
return s[x];
}
}
void merge(int x,int y){
int t1=find(x);
int t2=find(y);
if(t1!=t2)s[t1]=t2;
}
bool pd(int x,int y){
if(find(x)==find(y))return true;
else return false;
}
main(){
int t; cin>>t;
for(int i=1;i<=t;i++){
int m,x,y,l,n=0; cin>>m;
for(int i=0;i<=20000000;i++)s[i]=i;
bool flag=true;
for(int i=1;i<=m;i++){
cin>>x>>y>>l;
if(l)merge(x,y);
else if(pd(x,y)){cout<<"NO"<<endl; flag=false; break;}
else{n++; a[n].x=x; a[n].y=y;}
}
for(int i=1;i<=n;i++)
if(find(a[i].x)==find(a[i].y)){
cout<<"NO"<<endl;
flag=false;
break;
}
if(flag)cout<<"YES"<<endl;
}
return 0;
}
```)