并查集水题
离散化之后直接并查集合并，在不等时判断两者是否在同一个集合內即可
注意排序
贴代码：
#include <cstdio> #include <cmath> #include <cstring> #include <cstdlib> #include <iostream> #include <algorithm> #include <queue> #include <stack> #include <map> using namespace std; map <int,int> M1,M2; int tot=0; int T,n; struct Ques { int l,r,typ; friend bool operator < (Ques a,Ques b) { return a.typ>b.typ; } }q[100005]; int f[200005]; int siz[200005]; int findf(int x) { return x==f[x]?x:f[x]=findf(f[x]); } void init() { M1.clear(),M2.clear(),tot=0; for(int i=1;i<=2*n;i++)f[i]=i,siz[i]=1; } inline int read() { int f=1,x=0;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } int main() { T=read(); while(T--) { n=read();init(); for(int i=1;i<=n;i++) { q[i].l=read(),q[i].r=read(),q[i].typ=read(); M1[q[i].l]=M1[q[i].r]=1; } sort(q+1,q+n+1); map <int,int>::iterator it; for(it=M1.begin();it!=M1.end();it++)M2[it->first]=++tot; for(int i=1;i<=n;i++)q[i].l=M2[q[i].l],q[i].r=M2[q[i].r]; bool fl=0; for(int i=1;i<=n;i++) { int f1=findf(q[i].l),f2=findf(q[i].r); if(q[i].typ==1&&f1!=f2) { if(siz[f1]>siz[f2])f[f2]=f1,siz[f1]+=siz[f2]; else f[f1]=f2,siz[f2]+=siz[f1]; } else if(q[i].typ==0&&f1==f2){fl=1;break;} } if(fl)printf("NO "); else printf("YES "); } return 0; }