题目链接：https://www.luogu.org/problemnew/show/P1955
并查集操作，1e9要离散化，数组要开大一些，操作前先执行合并操作
样例好毒啊（全是排好序的）
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int maxn = 100010;
int fa[maxn], n, flag, T, b[maxn];
struct node{
int x, y, e;
}a[maxn];
bool cmp(node a, node b)
{
return a.e > b.e;
}
int find(int x)
{
return fa[x] == x ? x : fa[x] = find(fa[x]);
}
void init(int n)
{
for(int i = 1; i <= n; i++) fa[i] = i;
}
int main()
{
scanf("%d",&T);
while(T--)
{
int tot = 0;
memset(a, 0, sizeof(a));
memset(b, 0, sizeof(b));
memset(fa, 0, sizeof(fa));
scanf("%d",&n);
for(int i = 1; i <= n; i++)
{
scanf("%d%d%d",&a[i].x,&a[i].y,&a[i].e);
b[++tot] = a[i].x;
b[++tot] = a[i].y;
}
sort(b + 1, b + 1 + tot);
int m = unique(b + 1, b + 1 + tot) - b;
for(int i = 1; i <= n; i++)
{
a[i].x = lower_bound(b + 1, b + 1 + m, a[i].x) - b;
a[i].y = lower_bound(b + 1, b + 1 + m, a[i].y) - b;
}
init(m);
sort(a+1, a+1+n, cmp);
for(int i = 1; i <= n; i++)
{
flag = 1;
int fx = find(a[i].x), fy = find(a[i].y);
if(a[i].e == 1)
{
fa[fx] = fy;
}
else
{
if(fx == fy)
{
printf("NO\n");
flag = 0;
break;
}
}
}
if(flag) printf("YES\n");
}
return 0;
}