初一看是道并查集题。但是 的数据范围开数组一定会炸内存。但是我们注意到 的范围比较小，所以可以考虑用一种绝妙的优化空间的方法——离散化。
离散化
为了应对这种询问量少而编号特别大的情况，可以考虑把那些大数据映射到小数据中。
具体操作就是离散化三部曲。
- 排序
- 去重
- 二分查找对应位置
这样把旧位置映射到新位置上，就是离散化的过程。
cpp
for (int i = 1; i <= n; i++) {
scanf("%d%d%d", &data[i].x, &data[i].y, &data[i].e);
vec.push_back(data[i].x); // 使用 vector 来存储数据
vec.push_back(data[i].y);
}
sort(vec.begin(), vec.end()); // 排序
vec.erase(unique(vec.begin(), vec.end()), vec.end()); // 去重
for (int i = 1; i <= n; i++) {
data[i].x = lower_bound(vec.begin(), vec.end(), data[i].x) - vec.begin(); // 二分查找旧数据在新数组的位置，并把它赋值到原来的数组上
data[i].y = lower_bound(vec.begin(), vec.end(), data[i].y) - vec.begin(); // lower_bound 函数返回的是一个地址，把它减去 vec 的初始地址就是下标
}
// 这样进行一波操作后，data 数组就变成了离散化后的数组需要注意的是，并查集初始化需要使用新的数组长度，即 vec 的长度，为 vec.end() - vec.begin() 的值。
完整代码
cpp
#include <bits/stdc++.h>
using namespace std;
const int maxN = 2e5 + 10;
struct node {
int x, y, e;
bool operator < (const node &rhs) const {
return e > rhs.e;
}
} data[maxN];
int n, T;
int par[maxN];
void init(int len) {
for (int i = 1; i <= len; i++) par[i] = i;
}
int find(int x) {
return par[x] == x ? x : par[x] = find(par[x]);
}
bool same(int x, int y) {
return find(x) == find(y);
}
void unite(int x, int y) {
if (!same(x, y)) par[find(y)] = par[x];
}
int main() {
scanf("%d", &T);
while (T--) {
vector<int> vec;
bool flag = true;
memset(data, 0, sizeof(data));
memset(par, 0, sizeof(par)); // 并查集的 par 数组每次需要初始化
scanf("%d", &n);
for (int i = 1; i <= n; i++) {
scanf("%d%d%d", &data[i].x, &data[i].y, &data[i].e);
vec.push_back(data[i].x);
vec.push_back(data[i].y);
}
sort(vec.begin(), vec.end());
vec.erase(unique(vec.begin(), vec.end()), vec.end());
for (int i = 1; i <= n; i++) {
data[i].x = lower_bound(vec.begin(), vec.end(), data[i].x) - vec.begin();
data[i].y = lower_bound(vec.begin(), vec.end(), data[i].y) - vec.begin();
}
init(vec.end() - vec.begin()); // 以 vec 的长度初始化并查集
sort(data + 1, data + n + 1);
for (int i = 1; i <= n; i++)
if (data[i].e) unite(data[i].x, data[i].y); // 如果满足 e == 1 则合并
else if (same(data[i].x, data[i].y)) flag = false; // 否则判断它们是否在一个集合内，如果是则输出 NO
printf("%s\n", flag ? "YES" : "NO");
}
}