https://www.luogu.com.cn/problem/P1955离散化+并查集

1.读入数据存入离散化数组c

2.排序去重

3.将原数组更新为在离散化数组中的位置

4.对于e=1使用并查集合并，e=0保存下来

5.检查是否冲突，输出答案

AC代码：

#include<bits/stdc++.h>
using namespace std;
int t,n;
long long a[100050],b[100050],c[200050],fa[400050];
bool e[100050];
long long Find(long long x){
	if(fa[x]==x){
		return x;
	}
	else return fa[x]=Find(fa[x]);
}
void Union(long long x,long long y){
	long long u=Find(x),v=Find(y);
	if(u==v)return;
	fa[u]=v;
}
bool check(long long x,long long y){
	long long u=Find(x),v=Find(y);
	if(u==v)return 1;
	else return 0;
}
int main() {
	scanf("%d",&t);
	while(t--){
		scanf("%d",&n);
		int k=0,ans=1;
		for(int i=0;i<n;i++){
			int tmpe;
			scanf("%lld%lld%d",&a[i],&b[i],&tmpe);
			e[i]=(tmpe==1);
			c[k++]=a[i];
			c[k++]=b[i];
		}
		sort(c,c+k);
		k=unique(c,c+k)-c;
		for(int i=0;i<2*k;i++){
			fa[i]=i;
		}
		vector<pair<long long,long long>>ck;
		for(int i=0;i<n;i++){
			a[i]=lower_bound(c,c+k,a[i])-c;
			b[i]=lower_bound(c,c+k,b[i])-c;
			if(e[i]){
				Union(a[i],b[i]);
			}
			else{
				ck.push_back(make_pair(a[i],b[i]));
			}
		}
		for(auto i:ck){
			if(check(i.first,i.second)){
				ans=0;
				break;
			}
		}
		if(ans)printf("YES\n");
		else printf("NO\n");
	}
	return 0;
}