全RE求助!!!
查看原帖
全RE求助!!!
415961
Luo_gu_ykc楼主2021/12/15 22:38
#include<bits/stdc++.h>
using namespace std;
int t, fa[1000005], b[3000005];
//P1955 [NOI2015] 程序自动分析
struct node{
	int x, y, z;
}a[1000005];
bool cmp(node x, node y){
	return x.z > y.z;
}
int find(int x){
	if(fa[x] == x)
		return x;
	return fa[x] = find(fa[x]);
}
int main(){
	cin >> t;
	while(t--){
		int n, cnt = 0, v = 0;
		cin >> n;
		memset(a, 0, sizeof(a));
		memset(b, 0, sizeof(b));
		memset(fa, 0, sizeof(fa));
		for(int i = 1; i <= n; i++){
			cin >> a[i].x >> a[i].y >> a[i].z;
			b[++cnt] = a[i].x;
			b[++cnt] = a[i].y;
		}
		sort(b + 1, b + cnt + 1);
		int len = unique(b + 1, b + len + 1) - b - 1;
		for(int i = 1; i <= n; i++){
			a[i].x = lower_bound(b + 1, b + len + 1, a[i].x) - b;
			a[i].y = lower_bound(b + 1, b + len + 1, a[i].y) - b;
		}
		for(int i = 1; i <= len; i++)
			fa[i] = i;
		sort(a + 1, a + 1 + n, cmp);
		for(int i = 1; i <= n; i++){
			int fx = find(a[i].x);
			int fy = find(a[i].y);
			if(a[i].z == 1){
				fa[fx] = fy;
			}
			else{
				if(fx == fy){
					v = 1;
					puts("NO");
					break;
				}
			}
		}
		if(v == 0){
			puts("YES");
		}
	}
	return 0;
}
2021/12/15 22:38
加载中...