萌新求助!
查看原帖
萌新求助!
425074
ChevalierDeSangreal楼主2021/1/2 20:12

  萌新求助!!!

  为什么我加一个判断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;
} 
2021/1/2 20:12
加载中...