有n个变量和m个“相等”或“不相等”的约束条件，请你判定是否存在一种赋值方案满足所有m个约束条件。
输入
第一行一个整数T，表示数据组数。
接下来会有T组数据，对于每组数据：
第一行是两个整数n,m，表示变量个数和约束条件的个数。
接下来m行，每行三个整数a,b,e，表示第a个变量和第b个变量的关系：
若e=0则表示第a个变量不等于第b个变量；
若e=1则表示第a个变量等于第b个变量输出
输出T行，第i行表示第i组数据的答案。若第i组数据存在一种方案则输出"Yes"；否则输出"No"（不包括引号）。输入样例1
2
5 5
1 2 1
2 3 1
3 4 1
1 4 1
2 5 0
3 3
1 2 1
2 3 1
1 3 0
输出样例
Yes
No样例1解释：一共有2组数据，对于第一组数据，有5个约束：
变量1 = 变量2；变量2 = 变量3；变量3 = 变量4；变量1 = 变量4
变量2 ≠ 变量5
显然我们可以令
变量1=变量2=变量3=变量4=任意一个数值
变量5=任意一个和变量2不同的数值
故第一组数据输出"Yes"
这道题很明显可以用并查集来维护，思路很简单，我们可以将相等的变量放在一个并查集中，如果后面出现不相等的变量也在这个集合中，那显然是错了。为了使算法更高效，我们使用路径压缩和启发式合并来进行优化，路径压缩我在前一个博客里面写过了。而启发式搜索，虽然名字很高大上，但其核心思想很简单。
并查集的逻辑层面是一棵树，所以是有高度的，如果把一棵深度大的树的根节点接在了一棵深度小的树上，因为是直接把根节点接在另一个的根节点上，所以整棵树的深度为那一棵深度大的树的深度加一。而如果把一棵深度小的树的根节点接在了一棵深度大的树上，可直接接上，不影响深度。如果两个数深度一样，则将接完后的树的深度加一即可。所以考虑每次都将深度小的树接在深度大的树上，这就是启发式合并的原理。
经过了路径压缩和启发式合并之后，并查集的效率非常高，对 \(n\) 个元素的并查集进行一次操作的复杂度是\(O(\alpha (n))\)，这里的\(\alpha (n)\)是阿克曼函数的反函数。这个级别比\(O(logn)\)还要快。
代码：
#include <bits/stdc++.h>
using namespace std;
const int maxn = 10005;
int Father[maxn], Rank[maxn];
int find(int x) { //路径压缩
if(x != Father[x])
return Father[x] = find(Father[x]);
}
//启发式合并
void _union(int a, int b) { //我们倾向于将较矮的树插入到较高的树中
if(Rank[a] < Rank[b]) { //说明b树较高
Father[a] = b; //将a的父亲设置为b
} else { //如果a的树较高或者a和b一样高
Father[b] = a; //将b的父亲设置为a
if(b == a) {
Rank[a]++; //如果一样高，合并之后树的高度会增加1，所以将a的秩加一
}
}
}
string getAnswer(int n, int m, vector<int> A, vector<int> B, vector<int> E) {
for(int i = 1 ; i <= n ; ++i) { //先将数组初始化一下
Father[i] = i;
Rank[i] = 0;
}
int cnt = 0; //我们将相等的元素提到前面去
for(int i = 0 ; i < n ; ++i) {
if(E[i] == 1) { //将相等的条件移到前面，以免判断不相等的时候漏判
int t = E[cnt]; E[cnt] = E[i]; E[i] = t;
t = A[cnt]; A[cnt] = A[i]; A[i] = t;
t = B[cnt]; B[cnt] = B[i]; B[i] =t;
cnt++;
}
}
for(int i = 0 ; i < m ; ++i) {
int setA = find(A[i]);
int setB = find(B[i]);
if(E[i] == 0) { //如果两个元素不相等，但是在同一个集合中
if(setA == setB) //则返回no
return "No";
} else {
if(setA != setB) {
_union(setA, setB);
}
}
}
return "Yes";
}
int main() {
int T;
for (scanf("%d", &T); T--; ) {
int n, m;
scanf("%d%d", &n, &m);
vector<int> A, B, E;
for (int i = 0; i < m; ++i) {
int a, b, e;
scanf("%d%d%d", &a, &b, &e);
A.push_back(a);
B.push_back(b);
E.push_back(e);
}
printf("%s\n", getAnswer(n, m, A, B, E).c_str());
}
return 0;
}
Comments | NOTHING