并查集是一种非常有用的数据结构,它的主要功能是动态加边和查询两个点的连通性。在开始学习并查集之前,可以先看看一个故事,这个故事看完了,并查集也就学的差不多了。传送门: 并查集故事

并查集的本质是维护一个森林,而森林里的每一棵树里的每一个节点都会维护它的父亲节点。

Slow Find Slow Union

想像一下,如果我们不用并查集这种数据结构,而是用普通的集合做find和union操作,会是什么情况(解释一下,find操作用来判断两者是不是在同一个集合,union操作就是将两个集合进行合并)

以上的每一个格子都表示一个集合,从操作上我们可以明显的看出,每次合并一个集合,都需要将一个集合里的元素全部移动到另一个集合中去。find操作也是很慢的,每次都需要将集合里面的一个元素和另一个集合里面的元素作比较。

有没有改进的方法呢?那当然是有的

Quick Find Slow Union

解决的方法就是使用数组下标来进行索引:

这样就可以快速实现find操作,如果你将我画的表格看成一个一维数组,就是将所有元素都往左推,那么关系:fa[A] = B 这就表示A是属于B这个集合的,而B就是代表元,也就是故事中的掌门。可以看到find操作为常数时间,但是Union操作还是很慢。

有没有改进的方法呢?那当然是有的 * 2

Mid Find Quick Union

我们将集合间的关系用数组表示之后: fa[5] = 0,说明5的爸爸是0,fa[0] = 0,说明0是这个集合的代表元。集合种元素的关系如下图,位于根节点的位置是代表元。

当我们要做find操作时,比如需要知道5是在哪个集合,只需要一直往上去找就好了,如果我们要做union操作:将0所代表的集合与1所代表的集合合并,我们就可以这样来操作:

这样就将两个集合合并了。

现在,我们还有一个问题,能不能将find操作也优化一下呢?那当然是可以的的 * 3

Quick Find Quick Union

当我们在进行查询操作的时候,我们很可能遇到这样的情况:

当我们要进行find(3)操作时,我们需要一步一步地往上找,这就增加了时间开销,这个时候,我们就可以使用路径压缩来进行解决。如果我们能将路径变成下图的情况,那是再好不过的:

这种操作就叫做路径压缩,我们希望我们所构造的关系树时越来 越 " 矮 ",更加一般的情况:

路径压缩

现在,我们的find操作比刚才的find要快上不少了。

代码

并查集并没有一个固定的代码模板,在题目中千变万化,了解其思想时最重要的

#include<iostream>  
using namespace std;
const int MAXN = 10005;
int fa[MAXN];
int find(int x) {
	while(x != fa[x])
		x = fa[x];
	return x;
}
void union(int x , int y)  {  //合并x元素和y元素的两个集合 
	fa[find(a)] = find(b);		 
} 
int main(){
	for(int i = 0 ; i < n ; ++i)  //n为数据规模 
		fa[i] = i;  //初始化 
}

路径压缩:将x的祖先设置为x的父亲

#include<iostream>  
using namespace std;
const int MAXN = 10005;
int fa[MAXN];
int find(int x) {
    if(x != fa[x])    //查找的过程中就可以进行路径压缩
        return fa[x] = find(fa[x]);
}
void union(int x , int y)  {  //合并x元素和y元素的两个集合 
	fa[find(a)] = find(b);		 
} 
int main(){
	for(int i = 0 ; i < n ; ++i)  //n为数据规模 
		fa[i] = i;  //初始化 
}

立志成为一名攻城狮
最后更新于 2020-03-13