<—点个赞吧QwQ
宣传一下算法提高课整理{:target=”_blank”}
incra原帖写的太草率了,无论是文档还是注释,本帖是对原帖的详细化展开
并查集
所有输入分两类:等式$(e=1)$和不等式$(e=0)$,依据等式的传递性,$x_1~=~x_2,~x_2~=~x_3$可一同推出$x_1~=~x_3$,由此用并查集将所有等式中的两个变量合并到一起,这样一来处于同一集合中的变量应该两两相等,处于不同集合中的两个变量才有可能不相等
由于每一行输入时,已经给定了此表达式的$x_i$和$x_j$是相等关系还是不等关系,故对于每一行等式,直接当场让两个变量相等$(equalize)$,对于不等式,则单独将两个变量成对保存到线性表$neq(not~equal)$中,然后遍历所有不等式的变量对,发现相等的就标记并结束遍历,最后根据标记输出”YES”还是”NO”
由于$x_i$的$i$最大可取$10^9$,故把每一个值都直接对应到数组下标是不现实的,需要按上图的方式,人为的按照他们的出现顺序为它们标记索引(index),这件事可交给哈希表去做,确定了每个变量的索引之后,就可以按照常规的并查集方法解决了
C++ 代码
#include <iostream>
#include <algorithm>
#include <numeric>
#include <functional>
#include <unordered_map>
#include <vector>
#include <string>
using namespace std;
using Expr = pair<int, int>;//每一组不等关系的表达式(Expression)都可以抽象化为一个整型对组(pair)
vector<Expr> neq;//不等式表
vector<int> ori;//并查集用源节点表
unordered_map<int, int> idx;//用于映射索引的哈希表
int tot = 1;//tot每次给新出现的变量赋索引之后都会自增(不用这个也许可以)
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int t;
cin >> t;
//求变量自身的索引值
auto getIndex = [=](int x)->int {
//未曾出现过的需要赋予新索引
if (idx.find(x) == idx.end()) idx[x] = tot++;
return idx[x];
};
//针对索引值查找
function<int(int)> find = [&find](int x)->int {
if (x != ori[x]) ori[x] = find(ori[x]);
return ori[x];
};
//判断变量是否相等
auto isEqual = [=](int x, int y)->bool {
//要求出它们的索引值才能find
return find(getIndex(x)) == find(getIndex(y));
};
//使两个变量相等
auto equalize = [=](int x, int y) {
//同样求索引值
int pr = find(getIndex(x)), nx = find(getIndex(y));
if (pr == nx) return;
ori[pr] = nx;
};
while (t--) {
//每组测试用例分别独立,需要清空idx和neq
idx.clear();
neq.clear();
tot = 1;
int n;
cin >> n;
//n个表达式最多可以产生2*n个变量
ori.resize(2 * n + 1);
//作用是以0为初值,依次给整条表内的元素自增赋值,形成(0,1,2,3,...),位于<numeric>头文件中
iota(ori.begin(), ori.end(), 0);
while (n--) {
int i, j, e;
cin >> i >> j >> e;
if (e == 1) equalize(i, j);//等式,直接让他俩相等
else neq.push_back({ i,j });//不等式,脱机处理
}
string res = "YES";
//遍历不等式
for (auto& [i, j] : neq) {
//本应不等却相等,无法成立
if (isEqual(i, j)) {
res = "NO";
break;
}
}
cout << res << endl;
}
return 0;
}
再附上两帖中代码的运行时间效率对比
我没有读入优化()
下次记得带上()