在实现程序自动分析的过程中，常常需要判定一些约束条件是否能被同时满足。考虑一个约束满足问题的简化版本：假设 x1,x2,x3,… 代表程序中出现的变量，给定 n 个形如 xi=xj 或 xi≠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≤105, 1≤i,j≤109
输入样例：
2
2
1 2 1
1 2 0
2
1 2 1
2 1 1
输出样例：
NO
YES
解析：
每个问题给的条件是相互独立的，也就是和顺序无关，可先进行“e=1” ，再进行“e=2”。
当进行“e=1”时，是并查集的合并；文章来源：https://www.toymoban.com/news/detail-678394.html
当进行“e=2”时，也就是相当于变相的并查集查询。文章来源地址https://www.toymoban.com/news/detail-678394.html
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N=2e6+10;
int p[N];
map <int,int> k;
int cnt;
int get(int x)
{
if (k.count(x)==0) k[x]=++cnt; //离散化
return k[x];
}
int find(int x)
{
if (x!=p[x]) p[x]=find(p[x]);
return p[x];
}
struct node
{
int a,b,e;
}s[N];
bool cmp(node x,node y)
{
return x.e>y.e;
}
signed main()
{
int t;
scanf("%lld",&t); //读入的数据较多，用scanf读入
while (t--)
{
int n;
scanf("%lld",&n);
for (int i=1;i<=2e6;i++) p[i]=i;
k.clear(); //记得要清空哦！
cnt=0;
for (int i=0;i<n;i++)
{
int x,y;
scanf("%lld%lld%lld",&x,&y,&s[i].e);
s[i].a=get(x); //离散化，map即可
s[i].b=get(y);
}
bool falg=0;
for (int i=0;i<n;i++)
if (s[i].e==1)
{
if (find(s[i].a)!=find(s[i].b)) p[find(s[i].a)]=find(s[i].b);
}
for (int i=0;i<n;i++)
if (s[i].e==0)
{
if (find(s[i].a)==find(s[i].b))
{
falg=1;
break;
}
}
if (!falg) puts("YES");
else puts("NO");
}
return 0;
}到了这里，关于程序自动分析——并查集+离散化的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
