70分求调
查看原帖
70分求调
930325
Li_Yichen楼主2024/4/13 21:16
#include<bits/stdc++.h>
using namespace std;
#define int long long
int t;
int n;
int cnt;
int tmp[200005];
int father[100005];
int e[100005],x[100005],y[100005];
void init(){
	cnt = 0;
	memset(tmp,0,sizeof(tmp));
	memset(e,0,sizeof(e));
	memset(x,0,sizeof(x));
	memset(y,0,sizeof(y));
	for(int i=0;i<=n;i++){
		father[i] = i;
	}
}
int find(int x){
	if(father[x] == x) return x;
	return father[x] = find(father[x]);
}
void merge(int x,int y){
	int q = find(x);
	int p = find(y);
	if(q != p){
		father[q] = p;
	}
}
signed main(){
	cin >> t;
	while(t--){
		cin >> n; 
		init();
		for(int i=1;i<=n;i++){
			cin >> x[i] >> y[i] >> e[i];
			tmp[++cnt] = x[i];
			tmp[++cnt] = y[i];
		}
		//离散化 
		sort(tmp+1,tmp+1+cnt);
		int len = unique(tmp+1,tmp+1+cnt) - tmp;
		for(int i=1;i<=n;i++){
			x[i] = lower_bound(tmp+1,tmp+1+len,x[i]) - tmp;
			y[i] = lower_bound(tmp+1,tmp+1+len,y[i]) - tmp;
			//cout << x[i] << " " << y[i] << endl;
		}
		//并查集模板
		for(int i=1;i<=n;i++){
			if(e[i] == 1) merge(x[i],y[i]);
		} 
		int flag = 1;
		for(int i=1;i<=n;i++){
			if(e[i] == 0){
				if(find(x[i]) == find(y[i])){
					flag = 0;
					cout << "NO" << endl;
					break;
				}
			}
		}
		if(flag) cout << "YES" << endl;
	}
	return 0;
}

2024/4/13 21:16
加载中...