【题目来源】
洛谷：[P1955 NOI2015] 程序自动分析 - 洛谷
【题目描述】
在实现程序自动分析的过程中，常常需要判定一些约束条件是否能被同时满足。
考虑一个约束满足问题的简化版本：假设 \(x_1,x_2,x_3,\dots\) 代表程序中出现的变量，给定 \(n\) 个形如 \(x_i=x_j\) 或 \(x_i\neq x_j\) 的变量相等/不等的约束条件，请判定是否可以分别为每一个变量赋予恰当的值，使得上述所有约束条件同时被满足。例如，一个问题中的约束条件为：\(x_1=x_2,x_2=x_3,x_3=x_4,x_4\neq x_1\)，这些约束条件显然是不可能同时被满足的，因此这个问题应判定为不可被满足。
现在给出一些约束满足问题，请分别对它们进行判定。
【输入】
输入的第一行包含一个正整数 \(t\)，表示需要判定的问题个数。注意这些问题之间是相互独立的。
对于每个问题，包含若干行：
第一行包含一个正整数 \(n\)，表示该问题中需要被满足的约束条件个数。接下来 \(n\) 行，每行包括三个整数 \(i,j,e\)，描述一个相等/不等的约束条件，相邻整数之间用单个空格隔开。若 \(e=1\)，则该约束条件为 \(x_i=x_j\)。若\(e=0\)，则该约束条件为 \(x_i\neq x_j\)。
【输出】
输出包括 \(t\) 行。
输出文件的第 \(k\) 行输出一个字符串 YES 或者 NO（字母全部大写），YES 表示输入中的第 \(k\) 个问题判定为可以被满足，NO 表示不可被满足。
【输入样例】
2
2
1 2 1
1 2 0
2
1 2 1
2 1 1
【输出样例】
NO
YES
【解题思路】
【算法标签】
《洛谷 P1955 程序自动分析》 #并查集# #离散化# #哈希,hash# #NOI# #2015#
【代码详解】
#include <bits/stdc++.h>
using namespace std;const int N = 100005; // 定义最大数据量int t, n, cnt; // t: 测试用例数, n: 每个用例的关系数, cnt: 离散化计数器
int a[N], b[N], e[N]; // a,b: 关系中的两个元素, e: 关系类型(1-同集合,0-不同集合)
int p[N*2]; // 并查集父节点数组(开两倍空间)
unordered_map<int, int> mp; // 离散化映射表/*** 查找根节点(带路径压缩)* @param x 当前节点* @return 根节点*/
int find(int x)
{return p[x] == x ? x : p[x] = find(p[x]);
}/*** 离散化函数* @param x 原始值* @return 离散化后的值*/
int get(int x)
{if (mp.count(x) == 0) mp[x] = ++cnt; // 如果未映射过，分配新编号return mp[x];
}int main()
{cin >> t; // 输入测试用例数while (t--) {cnt = 0; // 重置离散化计数器mp.clear(); // 清空映射表cin >> n; // 输入关系数// 初始化并查集(开两倍空间)for (int i = 1; i <= n * 2; i++) {p[i] = i;}// 输入并离散化所有关系for (int i = 1; i <= n; i++) {cin >> a[i] >> b[i] >> e[i];a[i] = get(a[i]);b[i] = get(b[i]);}// 处理同集合关系(合并集合)for (int i = 1; i <= n; i++) {if (e[i] == 1) {int x = find(a[i]), y = find(b[i]);if (x != y) p[x] = y; // 合并集合}}// 检查不同集合关系是否矛盾bool flag = true;for (int i = 1; i <= n; i++) {if (e[i] == 0 && find(a[i]) == find(b[i])) {flag = false; // 发现矛盾break;}}// 输出结果flag ? puts("YES") : puts("NO");}return 0;
}
【运行结果】
2
2
1 2 1
1 2 0
NO
2
1 2 1
2 1 1
YES