程序自动分析——并查集+离散化

在实现程序自动分析的过程中，常常需要判定一些约束条件是否能被同时满足。考虑一个约束满足问题的简化版本：假设 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”时，是并查集的合并；

当进行“e=2”时，也就是相当于变相的并查集查询。

#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;
}