测试地址：程序自动分析
做法：这个题目一看就很并查集是不是，先把相等的元素并成一个集合，然后再判断不等的条件，如果两个元素在同一个集合，直接输出NO，检查完后没有冲突的就输出YES。然而还有一点，元素的标号本身达到了10^9，直接用并查集存不下这么多，然而条件只有10^6个，也就是说最多存在2*10^6个有效元素，因此把所有在条件中出现过的元素标号排个序，然后离散化，就可以用并查集求解了。
以下是本人代码：
#include <cstdio> #include <cstdlib> #include <cstring> #include <iostream> #include <algorithm> using namespace std; struct forsort{int val,pos;} f[2000010]; int T,n,tot,op[1000010],p[1000010][2],fa[2000010]; bool cmp(forsort a,forsort b) { return a.val<b.val; } int find(int x) { int r=x,i=x,j; while(fa[r]!=r) r=fa[r]; while(i!=r) {j=fa[i];fa[i]=r;i=j;} return r; } void merge(int x,int y) { int fx=find(x),fy=find(y); fa[fx]=fy; } int main() { scanf("%d",&T); while(T--) { scanf("%d",&n); for(int i=1,a,b;i<=n;i++) { scanf("%d%d%d",&a,&b,&op[i]); f[(i<<1)-1].val=a,f[i<<1].val=b; f[(i<<1)-1].pos=f[i<<1].pos=i; } sort(f+1,f+(n<<1)+1,cmp); memset(p,0,sizeof(p)); tot=0; for(int i=1;i<=n<<1;i++) { if (i==1||(i>1&&f[i].val!=f[i-1].val)) tot++; if (!p[f[i].pos][0]) p[f[i].pos][0]=tot; else p[f[i].pos][1]=tot; } for(int i=1;i<=tot;i++) fa[i]=i; for(int i=1;i<=n;i++) if (op[i]) merge(p[i][0],p[i][1]); bool flag=1; for(int i=1;i<=n;i++) if (!op[i]) { if (find(p[i][0])==find(p[i][1])) {printf("NO\n");flag=0;break;} } if (flag) printf("YES\n"); } return 0; }
