题目大意： 对于每一个式子，要么是 xi = xj 的形式，要么是 xi ̸= xj 的形式。现在我给出这 n 个式子，你要告诉我，这 n 个式子是否可能同时成立。
解题思路： 1.首先，如果被要求相等的式子在后面被要求不相等显然是不合法的，不相等同理。 2.我们可以想到用并查集维护等式的关系，如果被要求相等就加入并查集，然后用并查集验证不等的情况，如果式子在相等的集合中，就输出NO。 3.小技巧:对于多次询问的问题，最好用函数解决，因为return 很方便。 数据离散化可用lower__bound();在离散化之前 应该用一个数组保存这两组数据。
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #define MAXN 100005 using namespace std; int t,r1,r2,a[MAXN],b[MAXN],c[MAXN],f[MAXN<<1],n,tmp[MAXN<<1]; int find(int x){ return f[x]==x?x:f[x]=find(f[x]); } void work(){ scanf("%d",&n); for (int i=1;i<=2*n;i++) f[i]=i; for (int i=1;i<=n;i++) { scanf("%d%d%d",&a[i],&b[i],&c[i]); tmp[i*2-1]=a[i];tmp[i*2]=b[i];//为离散化做准备 } sort(tmp+1,tmp+2*n+1);//离散化 for (int i=1;i<=n;i++) { a[i]=lower_bound(tmp+1,tmp+2*n+1,a[i])-tmp; b[i]=lower_bound(tmp+1,tmp+2*n+1,b[i])-tmp; } for (int i=1;i<=n;i++) if (c[i]){ r1=find(a[i]);r2=find(b[i]); if (r1!=r2) f[r1]=r2; } for (int i=1;i<=n;i++) { if (c[i]) continue ; if (find(a[i])==find(b[i])) { printf("NO\n");return ; } } printf("YES\n"); } int main(){ cin>>t; loop: while(t--){ work(); } return 0; }