离散化+并查集
题意:给定n个等式关系,判断是否存在矛盾
我们可以将$=$的变量看成一个集合,若两个变量是$!=$且两个变量已经在一个集合里面,则说明矛盾了。
该题因为变量的值很大,$1-10^9$,并查集的数组并不能开这么大,且一共有$n$个等式关系,最大有$2n$个变量,则需要通过离散化后使用并查集。
- 读入,并进行离散化
- 先将所有等式关系为$=$的变量合并成一个集合
- 枚举$!=$的关系,判断是否存在矛盾
时间复杂度$O(NC)$,空间复杂度$O(N)$。$C$为并查集的常数
AC代码
#include <iostream>
#include <unordered_map>
using namespace std;
const int N = 1e5 + 10;
struct Q{
int x, y, d;
}queries[N];
int T, n, idx;
unordered_map<int, int> h; //变量id和并查集id的映射
int p[N * 2];
int find(int x) {
if (x != p[x]) p[x] = find(p[x]);
return p[x];
}
int main() {
cin >> T;
while (T --) {
h = {};
idx = 0;
//读入
cin >> n;
for (int i = 0 ; i < n ; i ++) {
int x, y, d;
cin >> x >> y >> d;
queries[i] = {x, y, d};
if (!h.count(x)) h[x] = ++ idx;
if (!h.count(y)) h[y] = ++ idx;
}
//初始化并查集
for (int i = 1 ; i <= idx ; i ++) p[i] = i;
//合并=关系
for (int i = 0 ; i < n ; i ++) {
if (queries[i].d) {
int a = h[queries[i].x], b = h[queries[i].y];
p[find(a)] = find(b);
}
}
//枚举!=关系
bool res = true;
for (int i = 0 ; i < n ; i ++) {
if (!queries[i].d) {
int a = h[queries[i].x], b = h[queries[i].y];
int pa = find(a), pb = find(b);
if (pa == pb)
res = false;
}
}
if (res) cout << "YES\n";
else cout << "NO\n";
}
}