【BZOJ-4195】程序自动分析

#include <bits/stdc++.h>
using namespace std;

const int N = 1 << 20;
pair<int,int> un[N];
int n, num, tot, x[N], y[N], fa[N<<1], d[N<<1], op[N];

void discrete(int tot) {
	sort(d+1,d+tot+1);
	int m = unique(d+1, d+tot+1) - d - 1;
	for (int i = 1; i <= n; ++i) {
		x[i] = lower_bound(d+1,d+m+1,x[i]) - d;
		y[i] = lower_bound(d+1,d+m+1,y[i]) - d;
	}
}

int get(int x) {
	if (x == fa[x]) return x;
	return fa[x] = get(fa[x]);
}

void merge(int x,int y) {
	fa[get(x)] = get(y);
}

int main() {
	int T; cin >> T;
	while (T--) {
		cin >> n; tot = 0, num = 0;
		for (int i = 1; i <= 2*n; ++i) {
			fa[i] = i;
		}
		for (int i = 1; i <= n; ++i) {
			scanf ("%d %d %d",&x[i], &y[i], &op[i]);
			d[++tot] = x[i], d[++tot] = y[i];
		}
		discrete(tot);
		for (int i = 1; i <= n; ++i) {
			if (op[i] == 1) merge(x[i],y[i]);
			else  un[++num] = make_pair(x[i], y[i]);
		}
		bool fail = true;
		for (int i = 1; i <= num; ++i) {
			int x = get(un[i].first);
			int y = get(un[i].second);
			if (x == y) {
				fail = false; break;
			}
		}
		if (fail) puts("YES");
		else  puts("NO");
	}
	return 0;
}
/*
2
2
1 2 1
1 2 0
2
1 2 1
2 1 1
*/