有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;
}
立志成为一名攻城狮
最后更新于 2020-03-14