地址 https://www.acwing.com/problem/content/239/
在实现程序自动分析的过程中,常常需要判定一些约束条件是否能被同时满足。
考虑一个约束满足问题的简化版本：假设x1,x2,x3,…x1,x2,x3,…代表程序中出现的变量，给定n个形如xi=xjxi=xj或xi≠xjxi≠xj的变量相等/不等的约束条件，请判定是否可以分别为每一个变量赋予恰当的值，使得上述所有约束条件同时被满足。
例如，一个问题中的约束条件为：x1=x2，x2=x3，x3=x4，x1≠x4x1=x2，x2=x3，x3=x4，x1≠x4，这些约束条件显然是不可能同时被满足的，因此这个问题应判定为不可被满足。
现在给出一些约束满足问题，请分别对它们进行判定。
输入格式
输入文件的第1行包含1个正整数t，表示需要判定的问题个数，注意这些问题之间是相互独立的。
对于每个问题，包含若干行：
第1行包含1个正整数n，表示该问题中需要被满足的约束条件个数。
接下来n行，每行包括3个整数i,j,e，描述1个相等/不等的约束条件，相邻整数之间用单个空格隔开。若e=1，则该约束条件为xi=xjxi=xj；若e=0，则该约束条件为xi≠xjxi≠xj。
输出格式
输出文件包括t行。
输出文件的第k行输出一个字符串“YES”或者“NO”（不包含引号，字母全部大写），“YES”表示输入中的第k个问题判定为可以被满足，“NO”表示不可被满足。
数据范围
1≤n≤10000001≤n≤1000000
1≤i,j≤1000000000
输入样例： 2 2 1 2 1 1 2 0 2 1 2 1 2 1 1 输出样例： NO YES
解法
首先 各个元素如果只给出任意相等信息 那是没有冲突的
只有给出两个元素不相等 再去查找之前已经有了相等信息
或者给出相等信息 再去查找之前有了不相等信息 才是有冲突的（相等信息是可以在元素间传递的）
那么使用并查集就能很快的得出冲突与否
本道题目额外拐了一个弯的点在于
数值取值 为1e9 但是不需要连续排列 那么久要考虑元素的离散化
每当获取一个元素值的时候 在容器哈希里面查找是否之前已经使用过该数值 未记录则记录该数值 但是使用索引来表示该值
cin >> x >> y >> e;
query[i] = { get(x),get(y),e };
int get(int x)
{
if (S.count(x) == 0) S[x] = ++n;
return S[x];
}
其余均是常规并查集操作
代码如下
1 // 2222.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。 2 // 3 4 #include "pch.h" 5 6 #include <unordered_map> 7 #include <iostream> 8 #include <vector> 9 10 using namespace std; 11 12 const int N = 2000010; 13 14 int n; int m; 15 int p[N]; 16 unordered_map<int, int> S; 17 18 struct Query { 19 int x, y; 20 int e; 21 }query[N]; 22 23 int get(int x) 24 { 25 if (S.count(x) == 0) S[x] = ++n; 26 return S[x]; 27 } 28 29 30 int find(int x) 31 { 32 if (p[x] != x) p[x] = find(p[x]); 33 34 return p[x]; 35 } 36 37 38 39 int main() 40 { 41 int T; 42 cin >> T; 43 44 while (T--) { 45 n = 0; 46 S.clear(); 47 cin >> m; 48 for (int i = 0; i < m; i++) { 49 int x, y, e; 50 cin >> x >> y >> e; 51 query[i] = { get(x),get(y),e }; 52 } 53 54 for (int i = 1; i <= n; i++) p[i] = i; 55 56 57 //合并所有相等约束条件 58 for (int i = 0; i < m; i++) { 59 if (query[i].e == 1) { 60 int pa = find(query[i].x), pb = find(query[i].y); 61 p[pa] = pb; 62 } 63 } 64 65 //检查所有不等于条件 66 bool has_conflict = false; 67 for (int i = 0; i < m; i++) { 68 if (query[i].e == 0) { 69 int pa = find(query[i].x), pb = find(query[i].y); 70 if (pa == pb) { 71 has_conflict = true; 72 break; 73 } 74 } 75 } 76 77 if (1 == has_conflict) puts("NO"); 78 else puts("YES"); 79 80 } 81 82 83 return 0; 84 }