题目：
在实现程序自动分析的过程中,常常需要判定一些约束条件是否能被同时满足。
考虑一个约束满足问题的简化版本：假设x1,x2,x3,…代表程序中出现的变量，给定n个形如xi=xjxi=xj或xi≠xjxi≠xj的变量相等/不等的约束条件，请判定是否可以分别为每一个变量赋予恰当的值，使得上述所有约束条件同时被满足。
例如，一个问题中的约束条件为：x1=x2，x2=x3，x3=x4，x1≠x4，这些约束条件显然是不可能同时被满足的，因此这个问题应判定为不可被满足。
现在给出一些约束满足问题，请分别对它们进行判定。
输入文件的第1行包含1个正整数t，表示需要判定的问题个数，注意这些问题之间是相互独立的。
对于每个问题，包含若干行：
第1行包含1个正整数n，表示该问题中需要被满足的约束条件个数。
接下来n行，每行包括3个整数i,j,e，描述1个相等/不等的约束条件，相邻整数之间用单个空格隔开。若e=1，则该约束条件为xi=xj；若e=0，则该约束条件为xi≠xj。
输出文件包括t行。
输出文件的第k行输出一个字符串“YES”或者“NO”（不包含引号，字母全部大写），“YES”表示输入中的第k个问题判定为可以被满足，“NO”表示不可被满足。
1≤n≤10000001≤i,j≤1000000000
解题报告：涉及到了多个元素是否相等的问题，且这个问题具有连通传递性，这个时候并查集就体现出来了，并查集可以求解多个元素之间的连通性，但是给定的i，j的范围太大了，根本开不了far数组进行存储，所以就要进行一下离散化，将i，j的表示缩小到1-2n之间，之后就是正常的并查集操作了，需要注意的1，0操作代表的含义。
ac代码：
1 //from:Onion 2 //acwing 237 程序自动分析 并查集+离散化 3 #include<iostream> 4 #include<cstring> 5 #include<cstdio> 6 #include<algorithm> 7 #include<cmath> 8 using namespace std; 9 typedef long long ll; 10 11 const int maxn=1e6+100; 12 13 int far[maxn]; 14 int a[maxn],b[maxn],c[maxn]; 15 int mp[maxn<<1]; 16 17 int find(int x) 18 { 19 if(far[x]==x) 20 return far[x]; 21 else 22 return far[x]=find(far[x]); 23 } 24 25 int n,t; 26 int main() 27 { 28 scanf("%d",&t); 29 while(t--) 30 { 31 bool flag=false; 32 int cnt=0; 33 memset(a,0,sizeof(a)); 34 memset(b,0,sizeof(b)); 35 memset(c,0,sizeof(c)); 36 memset(mp,0,sizeof(mp)); 37 scanf("%d",&n); 38 for(int i=1;i<=n;i++) 39 { 40 scanf("%d%d%d",&a[i],&b[i],&c[i]); 41 mp[cnt++]=a[i]; 42 mp[cnt++]=b[i]; 43 } 44 sort(mp,mp+cnt); 45 for(int i=1;i<=cnt;i++) 46 far[i]=i; 47 for(int i=1;i<=n;i++) 48 { 49 if(c[i]==1) 50 { 51 int x=lower_bound(mp,mp+cnt,a[i])-mp; 52 int y=lower_bound(mp,mp+cnt,b[i])-mp; 53 int px=find(x); 54 int py=find(y); 55 if(px!=py) 56 far[px]=py; 57 } 58 } 59 for(int i=1;i<=n;i++) 60 { 61 if(c[i]==0) 62 { 63 int x=lower_bound(mp,mp+cnt,a[i])-mp; 64 int y=lower_bound(mp,mp+cnt,b[i])-mp; 65 int px=find(x); 66 int py=find(y); 67 if(px==py) 68 { 69 flag=true; 70 break; 71 } 72 } 73 } 74 if(flag) 75 { 76 printf("NO\n"); 77 } 78 else 79 printf("YES\n"); 80 } 81 }
