并查集 介绍

闲话

这篇只能算上是一个简略的介绍。我最初接触并查集是初中在学最小生成树时,不禁感叹其高效,感谢当时的师傅少峰。

 

并查集是什么

并查集,顾名思义,对集合的查询与并集操作。
引用百度百科中并查集的介绍:

在一些有N个元素的集合应用问题中,我们通常是在开始时让每个元素构成一个单元素的集合,然后按一定顺序将属于同一组的元素所在的集合合并,其间要反复查找一个元素在哪个集合中。这一类问题近几年来反复出现在信息学的国际国内赛题中,其特点是看似并不复杂,但数据量极大,若用正常的数据结构来描述的话,往往在空间上过大,计算机无法承受;即使在空间上勉强通过,运行的时间复杂度也极高,根本就不可能在比赛规定的运行时间(1~3秒)内计算出试题需要的结果,只能用并查集来描述。

并查集本质上是森林。一棵树表示一个独立的集合。

 

具体

原理

并查集本质上是森林,一棵树表示一颗集合,如果两个节点在同一个树中,那么在同一个集合。一棵树只有一个根节点,所以说,在同一棵树就是两个节点的根节点是同一个。并集就是将两个节点所在的树合并,一般的做法就是将一个根节点作为另一棵树根节点的孩子。

森林的描述

在一般的并查集中,我们用一个 Father[n] 数组维护一个森林。Father[n] 数组只是维护每一个点的父亲。因为一棵树表示一个集合,所以这棵树的结构究竟是怎么样的,我们并不关心。 所以,我们只维护每个节点的父亲节点。当一个节点的父亲节点是自己的时候,则说明这个节点是整棵树的根节点,也就是Father[n]\ ==\ n时。
在一开始的时候,我们将所有的节点的父亲赋值为他自己。表示所有的节点都还一颗独立的树,换句话说,每个节点都在各自的集合里。

查集

査集,也就是寻找该节点所在树的根节点。因为我们一开始就维护了 Father[n] 数组,所以我们根据 Father[n] 数组不停递归就好了。递归的终止条件就是 Father[n]\ ==\ n
代码

并集

并集就是将两棵树并到一起。做法就是将一个根节点作为另一棵树根节点的孩子。由于我们维护了 Father[n] 数组 ,直接修改就行。
代码只有一行。

复杂度

并查集合并的复杂度是 O(1) 的,查询的复杂度我也说不清,最坏情况是 O(n),最好是 O(1) 。当加入压缩路径的优化后,平均复杂度可以达到 O(1)

 

压缩路径优化

之前我们说过,

因为一棵树表示一个集合,所以这棵树的结构究竟是怎么样的,我们并不关心。

每次查询都是要从节点一直递归到根节点,就会出现一棵树退化成一个线性表的情况,那对我们来说很不理想。

做法

所我们在每次查询过后,将该叶子节点提到根节点处,这样下次查询将会更加快速。我们最想要的情况其实莫过于一棵树中只有一个根节点,其余都是叶子节点。当查询次数足够多时,我们完全可以达到这种情况,所以说当加入压缩路径的优化后,平均复杂度可以达到 O(1)

代码

压缩路径在查询的时候处理即可,所以修改查询代码就好。

例题

[POJ1611]The Suspects
[POJ2524]Ubiquitous Religions
[BZOJ1015][JSOI2008]星球大战starwar

 

并查集扩展

并查集有一种拓展叫做关系型并查集。可以用于二分图判定。
原理就是在维护树的时候,记录叶子和根节点的关系,及时更新。
从例题中可以理解。

例题

[POJ2492]A Bug's Life
[POJ1182]食物链
并查集删除 [UVa11987]Almost Union-Find

 

持续更新

发表评论

电子邮件地址不会被公开。 必填项已用*标注