并查集

并查集

并查集是一种树形的数据结构,顾名思义,它用于处理一些不交集的合并查询问题。
它支持两种操作:

  • 查找 (Find):确定某个元素处于哪个子集
  • 合并 (Union):将两个子集合合并成同一个集合

    初始化

1
2
3
4
5
6
7
8
void makeSet(int size)
{
for(int i = 0;i < size;i ++)
{
fa[i] = i;//i就在它本身的集合里
}
return;
}

查找

举个例子
几个家族进行宴会,但是家族普遍长寿,所以人数众多。由于长时间的分离以及年龄的增长,这些人逐渐忘掉了自己的亲人,只记得自己的爸爸是谁了,而最长者(称为“祖先”)的父亲已经去世,他只知道自己是祖先。为了确定自己是哪个家族,他们想出了一个办法,只要问自己的爸爸是不是祖先,一层一层的向上问,直到问到祖先。如果要判断两人是否在同一家族,只要看两人的祖先是不是同一人就可以了。
在这样的思想下,并查集的查找诞生了。我们可以用代码模拟这个过程。(路径压缩等会再说)

1
2
3
4
5
6
7
int fa[MAXN]; //记录某个人的爸爸是谁,特别规定,祖先的爸爸是他自己
int find(int x) //寻找x的祖先
{
if(fa[x] == x) //如果x是祖先则返回
return x;
else return find(fa[x]); //如果不是则x的爸爸问x的爷爷
}

显然这样最终会返回x的祖先。

路径压缩

这样的确可以达成目的,但是显然效率实在太低。为什么呢?因为我们使用了太多没用的信息,我关心的是我祖先是谁,我爸爸是谁没什么关系,这样一层一层找太浪费时间,不如我直接当祖先的儿子,问一次就可以出结果了。甚至祖先是谁都无所谓,只要这个人可以代表我们家族就能得到想要的效果。把在路径上的每个节点都直接连接到根上,这就是路径压缩。
于是用代码实现它。

1
2
3
4
5
6
int find(int x)
{
if(x != fa[x])//x不是自身的父亲,即x不是该集合的代表
fa[x] = find(fa[x]);//查找x的祖先直到找到代表,于是顺手路径压缩
return fa[x];
}

合并

宴会上,一个家族的祖先突然对另一个家族说:我们两个家族交情这么好,不如合成一家好了。另一个家族也欣然接受了。
我们之前说过,并不在意祖先究竟是谁,所以只要其中一个祖先变成另一个祖先的儿子就可以了。

1
2
3
4
5
6
7
8
void unionSet(int x,int y)//x与y所在家族合并
{
x = find(x);
y = find(y);
if(x == y)//原本就在一个家族里就不管了
return;
fa[x] = y;//把x的祖先变成y的祖先的儿子
}

启发式合并(选学)

一个祖先突然抖了机灵:“你们家族人比较少,搬家到我们家族里比较方便,我们要是搬过去的话太费事了。”
启发式合并是将深度小的集合合并到深度大的集合(也成为按秩合并),但是笔者认为这样做的话路径压缩之后它就失去意义了,或按照节点数量,这样还可以减少下次路径压缩的工作量。(反正启发式合并用得很少,路径压缩已经够快了。)

1
2
3
4
5
6
7
8
9
10
11
int size[N];//记录子树的大小
void unionSet(int x,int y)
{
int xx = find(x),yy = find(y);
if(xx == yy)
return;
if(size[xx] > size[yy])//保证小的合到大的里
swap(xx,yy);
fa[xx] = yy;
size[yy] += size[xx];
}

时间复杂度及空间复杂度

时间复杂度

同时使用路径压缩和启发式合并之后,并查集的每个操作平均时间仅为 $ O(α(n)) $ ,其中α为反阿克曼函数,其增长极其缓慢,也就是说其平均运行时间可以认为是一个很小的常数。感兴趣的同学可以自行百科。

空间复杂度

显然为 $ O(n) $

其他应用

最小生成树 Kruskal算法的优化

本文作者为JuicyMio,同时发表在OIwiki

除特别注明外,项目中除了代码部分均采用 (Creative Commons BY-SA 4.0) 知识共享署名-相同方式共享 4.0 国际许可协议 及附加的 The Star And Thank Author License 进行许可。