在实现程序自动分析的过程中,常常需要判定一些约束条件是否能被同时满足。
考虑一个约束满足问题的简化版本：假设x1,x2,x3,…代表程序中出现的变量，给定n个形如xi=xj或xi≠xj的变量相等/不等的约束条件，请判定是否可以分别为每一个变量赋予恰当的值，使得上述所有约束条件同时被满足。例如，一个问题中的约束条件为：x1=x2，x2=x3，x3=x4，x1≠x4，这些约束条件显然是不可能同时被满足的，因此这个问题应判定为不可被满足。
现在给出一些约束满足问题，请分别对它们进行判定。
Input
输入文件的第1行包含1个正整数t，表示需要判定的问题个数。注意这些问题之间是相互独立的。
对于每个问题，包含若干行：
第1行包含1个正整数n，表示该问题中需要被满足的约束条件个数。
接下来n行，每行包括3个整数i,j,e，描述1个相等/不等的约束条件，相邻整数之间用单个空格隔开。若e=1，则该约束条件为xi=xj；若e=0，则该约束条件为xi≠xj。
Output
输出文件包括t行。
输出文件的第k行输出一个字符串“YES”或者“NO”（不包含引号，字母全部大写），“YES”表示输入中的第k个问题判定为可以被满足，“NO”表示不可被满足。
Sample Input
2
2
1 2 1
1 2 0
2
1 2 1
2 1 1
Sample Output
NO
YES
HINT
在第一个问题中，约束条件为：x1=x2,x1≠x2。这两个约束条件互相矛盾，因此不可被同时满足。
在第二个问题中，约束条件为：x1=x2,x2=x1。这两个约束条件是等价的，可以被同时满足。
1≤n≤1000000
1≤i,j≤1000000000
思路：
并查集很好做，关键是加上离散化
因为数据规模(1e9)很大，超过了数组的上限。但数据据量(1e6) 开数组是刚刚好的
于是我们通过离散排序去重，只把数之间的关系表示出来即可
C++ lower_bound()函数
lower_bound() 函数用于在指定区域内查找不小于目标值的第一个元素。也就是说，使用该函数在指定范围内查找某个目标值时，最终查找到的不一定是和目标值相等的元素，还可能是比目标值大的元素。
底层代码
int lower_bound(int l,int r，int k){ while (l < r){ int mid=l+r >> 1; if (a[mid] >= k) r=mid; else l=mid+1; } return l; }
unique函数
它的功能是元素去重。即”删除”序列中所有相邻的重复元素(只保留一个)。此处的删除，并不是真的删除，而是指重复元素的位置被不重复的元素给占领了。由于它”删除”的是相邻的重复元素，所以在使用unique函数之前，一般都会将目标序列进行排序。
又是一道模板题，听懂了记得给个赞鼓励一下，码字不易，用爱发电。
上ac代码。
有事你就q我；QQ2917366383
学习算法
#include <cstdio> #include <iostream> #include <algorithm> #include <cstring> #include <string> #include <cmath> #include <cstdlib> using namespace std; int t,n,f[1000007],book[1000007*3]; //t表示t组数据，n表示有n个操作，f[]是我们并查集的数字，book[]是离散化的数组 struct node{ int x,y,e;//比较数据 }a[1000001]; bool cmp(node a,node b){ return a.e>b.e; }//排 序将e==1的放在前面 inline void first(int kkk){ for(int i=1;i<=kkk;i++) f[i]=i; }//初 始 化 int get(int x){ if(x==f[x]) return x; return f[x]=get(f[x]);//根 } int main(){ scanf("%d",&t); while(t--){ int tot=0; memset(book,0,sizeof(book));//离散初始化 memset(a,0,sizeof(a)); memset(f,0,sizeof(f)); int flag=1; scanf("%d",&n); for(int i=1;i<=n;i++){ scanf("%d %d %d",&a[i].x,&a[i].y,&a[i].e); book[tot++]=a[i].x; book[tot++]=a[i].y; } sort(book,book+tot);//排序 int reu=unique(book,book+tot)-book; //去重 for(int i=1;i<=n;++i){ a[i].x=lower_bound(book,book+reu,a[i].x)-book;//离散化 a[i].y=lower_bound(book,book+reu,a[i].y)-book; } first(reu); //初始化 sort(a+1,a+n+1,cmp); //按e排序 for(int i=1;i<=n;i++){ int r1=get(a[i].x); int r2=get(a[i].y); if(a[i].e){//！=0 f[r1]=r2; //就是我们的merge操作 } else if(r1==r2){ printf("NO\n"); flag=0; //如果不满足条件，标记为否 break; } } if(flag) printf("YES\n"); //都满足条件了 } return 0; }
