萌新求助!!!
为什么我加一个判断x == y的特判会WA,去掉这个特判以后就A掉了?我能理解为什么可以不加特判,但是加了特判我没想出来为什么会WA啊……可怜苣蒻我百思不得其解,求大佬解答。
这是特判之前的代码:
#include<iostream>
#include<cstdio>
using namespace std;
int f[300100], n, k, ans;
int find(int x){
if(f[x] == x)return x;
return f[x] = find(f[x]);
}
void merge(int x, int y){
f[find(x)] = find(y);
}
int main(){
scanf("%d%d", &n, &k);
for(int i=1;i<=n*3;i++)
f[i] = i;
for(int i=1;i<=k;i++){
int x, y, z;
scanf("%d%d%d", &z, &x, &y);
if((x > n)||(y > n)){
ans++;
continue;
}
if(z == 1){
if((find(x + n) == find(y))||(find(x) == find(y + n))){
ans++;
continue;
}
merge(x, y);
merge(x + n, y + n);
merge(x + n * 2, y + n * 2);
}
else{
if((find(x) == find(y))||(find(x) == find(y + n))){
ans++;
continue;
}
merge(x + n * 2, y + n);
merge(x + n, y);
merge(x, y + n * 2);
}
}
printf("%d", ans);
return 0;
}
这是特判之后的代码:
#include<iostream>
#include<cstdio>
using namespace std;
int f[300100], n, k, ans;
int find(int x){
if(f[x] == x)return x;
return f[x] = find(f[x]);
}
void merge(int x, int y){
f[find(x)] = find(y);
}
int main(){
scanf("%d%d", &n, &k);
for(int i=1;i<=n*3;i++)
f[i] = i;
for(int i=1;i<=k;i++){
int x, y, z;
scanf("%d%d%d", &z, &x, &y);
if((x > n)||(y > n)){
ans++;
continue;
}
if(x == y){
ans++;
continue;
}
if(z == 1){
if((find(x + n) == find(y))||(find(x) == find(y + n))){
ans++;
continue;
}
merge(x, y);
merge(x + n, y + n);
merge(x + n * 2, y + n * 2);
}
else{
if((find(x) == find(y))||(find(x) == find(y + n))){
ans++;
continue;
}
merge(x + n * 2, y + n);
merge(x + n, y);
merge(x, y + n * 2);
}
}
printf("%d", ans);
return 0;
}