50求调,悬赏2关注
查看原帖
50求调,悬赏2关注
445650
I_never_left楼主2023/7/3 20:12
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
const int N = 2000010;
const int Mod = 1000000007;

int n;
int f[N];
int lsh[N], cnt;
struct Node {
	int u, v, e;
}a[N];

bool mycmp(Node x, Node y) {
	return x.e > y.e;
}

int find(int x) {
	return f[x] == x ? x : f[x] = find(f[x]);
}

void solve() {
	cin >> n;
	for(int i = 1; i <= n; ++ i) f[i] = i;
	for(int i = 1; i <= n; ++ i) {
		cin >> a[i].u >> a[i].v >> a[i].e;
		lsh[++ cnt] = a[i].u;
		lsh[++ cnt] = a[i].v;
	}

	sort(a + 1, a + n + 1, mycmp);
	sort(lsh + 1, lsh + cnt + 1);
	cnt = unique(lsh + 1, lsh + cnt + 1) - lsh;
	for(int i = 1; i <= n; ++ i) {
		a[i].u = lower_bound(lsh + 1, lsh + cnt + 1, a[i].u) - lsh;
		a[i].v = lower_bound(lsh + 1, lsh + cnt + 1, a[i].v) - lsh;
	}

	for(int i = 1; i <= n; ++ i) {
		int x = find(a[i].u), y = find(a[i].v);
		if(a[i].e) {	
			if(x != y) f[x] = y;
		} else {
			if(x == y) {
				cout << "NO\n";
				return ;
			}
		}
	}
	cout << "YES\n";
}

int main() {
	int t; cin >> t;
	while(t --) solve();
	return 0;
}
2023/7/3 20:12
加载中...