题目链接:BZOJ 4195
在数据范围大,但实际数据个数不大的时候,采用离散化避免超出数组空间.
code:
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <map>
#include <string>
#include <vector>
using namespace std;
#define maxn 1000005
typedef long long ll;
typedef unsigned long long ull;
int fa[maxn * 2];
int x1[maxn];
int x2[maxn];
int s[maxn];
int n;
vector<int> b;
void init() {
b.clear();
for (int i = 0; i <= 2 * n; ++i) {
fa[i] = i;
}
}
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); }
void discrete() {
sort(b.begin(), b.end());
unique(b.begin(), b.end());
}
int query(int x) { return lower_bound(b.begin(), b.end(), x) - b.begin(); }
int main() {
int t;
cin >> t;
while (t--) {
cin >> n;
init();
for (int k = 1; k <= n; ++k) {
cin >> x1[k] >> x2[k] >> s[k];
b.push_back(x1[k]);
b.push_back(x2[k]);
}
discrete();
for (int i = 1; i <= n; ++i) {
if (s[i]) {
int x = query(x1[i]);
int y = query(x2[i]);
merge(x, y);
}
}
int flag = 0;
for (int i = 1; i <= n; ++i) {
if (!s[i]) {
int x = query(x1[i]);
int y = query(x2[i]);
if (get(x) == get(y)) {
cout << "NO" << endl;
flag = 1;
break;
}
}
}
if (!flag) {
cout << "YES" << endl;
}
}
return 0;
}