定义

并查集被认为是最简洁而优雅的数据结构之一。顾名思义,并查集是一类集合,它支持合并查询两种操作

从集合论出发

在集合 上定义一个等价关系(自反、对称、传递)~a~b表示元素ab等价。

根据等价关系,可以将集合 划分为若干个等价类 :

  • 一个元素a的等价类 的一个子集,它包含所有与a有关系的元素;
  • 等价类互不相见,所有等价类的并集就是集合 ;
  • 要确定是否a~b,只需要验证ab是否在同一个等价类中。

初始时,有N个元素,每个元素自成一个集合,元素互不相同,集合互不相交

1
{a},{b},{c},{d} ... {n}

对这些集合可以进行两种运算:

  • Find

    给定元素a,返回该元素所在集合的名字,即查询该元素属于哪个等价类。

  • Union

    给定一对元素ab,添加关系a~b;若这对元素不在同一个等价类中,由于等价关系的传递性,该运算将合并含有ab的两个等价类形成一个新的等价类。

    1
    {a, b},{c},{d} ... {n}

以上是并查集在集合论中的理论定义,有点抽象,为了将并查集具象化,可以映射到图论中。

引入图论

对于一个无向图,它的所有节点构成点集V、所有边构成边集E。若V中两个节点ab之间存在一条边,那么称ab连通关系。显然连通关系是集合V上的一个等价关系。根据连通关系,可以将点集V划分为若干个等价类,称之为连通分量

image-20211210155532228

那么上述操作就变成了:

  • Find

    给定某点a,查询a所属的连通分量,可以用来判断两点是否属于同一连通分量

  • Union

    给定一对点ab,在它们之间连接一条边,使两点连通,那么各自对应的连通分量也会连通成为一个新的连通分量。

从而我们为并查集在图论中找到了对应的实际意义:并查集可以用来表示和求解图中的连通性问题

构造

显然我们不关心也不需要知道等价类集合的名字,只需要在该等价类中选出一个代表元素x,给x赋予一个特殊地位,让集合中的其他元素从属于它。这就是并查集的重要思想所在。

现实来说,如果把集合比喻成一个帮派,那么代表元素就是选出的帮主,帮派中的其他帮众从属于帮主,帮众的事就是帮主的事。

那么上述两种操作就变成了:

  • 查询

    给定元素a,返回该元素的集合的代表元素;

    询问a所在帮派的帮主是谁,有事找帮主就行。

  • 合并

    给定一对元素ab,合并ab所在集合,在原来的两个代表元素中,选出新的代表元素。

    a和b想搞事情,必须由各自帮主出面,两个帮主比武后,按照约定好的规则合并两个帮派,二者之一成为新的帮主

下面用一个圆圈节点表示一个元素,箭头指向该元素的代表元素,举个例子看看并查集是如何运作的

  1. 初始时,有六个元素,每个元素自成一个集合,集合的代表元素当然就是该元素自己。

    六个散修各自为战,自成一派

img

  1. 对1号元素和3号元素执行合并操作,两个集合合并,1号成为新集合的代表元素

    1号和3号是各自帮派的帮主,直接比武,1号赢了成为合并帮派的新帮主

img

  1. 对2号元素和3号元素执行合并操作,两个集合合并,1号还是新集合的代表元素

    3号的帮主1号出来和2号比武又赢了,把2号收为帮众,帮派再次壮大。

preview

  1. 4、5、6号元素也进行了上述合并操作,形成一个新的集合,以4号为代表元素

    img

  2. 对2号元素和6号元素执行合并操作,

    2号和6号把各自的帮主叫出来比武,1号又赢了4号,4号输了认1号为帮主,4号手下的5号和6号也跟着投降了。此时大帮派的帮主是1号,但没有经过组织架构调整,5号和6号还归他们曾经的帮主4号管。

img

最后,形成了一个大帮派,可以看出这个大帮派的组织架构是树形结构。画成一棵树的形式如下:

img

这棵树的根节点就是集合的代表元素,要查询某元素所属结合的代表元素只需要一层一层访问父节点直到找到根节点。所以在这棵树中,只有父指针。

并查集由若干棵这样的不相交树构成,也即不相交森林

也就是说并查集的逻辑结构是树形结构,然而因为只有父指针,在具体实现时,只需要一个数组fa来存储每个节点中的父节点即可。

下面给出并查集最基础的实现:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class UFS{
private:
vector<int> fa; // 父指针数组
public:
// 构造函数,初始化
UFS(int n){
fa.resize(n);
for(int i=0;i<n;++i){
fa[i] = i; // 把单个节点的父节点设为自己
}
}

// 查询
int find(int x){
if(fa[x] != x){
return find(fa[x]); // 递归查询父节点,直到根节点
}
return fa[x];
}
// 合并
void Union(int x, int y){
fa[find(y)] = find(x); // 分别找到x、y的根节点,把y的根节点的父指针指向x的根节点
}
}

优化

从上面的实现中,发现Union操作实际上是两次find操作和一次赋值操作,那么Unionfind的时间复杂度是一样的,可以不做区分,统一认为是单次并查集操作

我们知道树形结构上的操作时间复杂度一般跟树的高度有直接关系。

当并查集中的元素个数为 n时,上述无优化的并查集的单次操作时间复杂度应为:

  • 平均

  • 最坏

    此时是一棵单支树,高度即为节点个数;或者说树退化成了链表

为了提高并查集操作的效率,应尽可能压扁树,即降低树的高度。所以考虑在查询和合并两个操作时,尽可能降低操作后树的高度。

路径压缩

img

如上图的树形结构,要查询元素2的根节点,需要一层一层往上,但我们其实是不关心路径上其他节点的,能一步到根是最好的。所以要压缩路径。

img

如图,把查询路径中所有节点的父节点都设为最终的根节点,下一次查询时就可以直接访问到根节点了。

具体进行路径压缩时,用递归的写法很容易实现上述思路:

1
2
3
4
5
6
7
8
int find(int x){
if(fa[x] != x){
// 多了一步把路径中的所有节点的父节点都设为根节点
fa[x] = find(fa[x]);
return fa[x]
}
return fa[x];
}

加上语法糖简写成一行代码

1
2
3
int find(int x){
return x == fa[x] ? x : (fa[x] = find(fa[x]));
}

路径查询的缺点是操作具有滞后性,只能在下一次查询时体现效果;另外,路径压缩可能会破坏树的结构。

按秩合并

路径压缩是在查询时进行,而且只压缩一条路径。所以经过路径压缩之后,并查集的结构可能仍比较复杂。因此我们考虑对合并操作进行优化。

上面在讲合并操作时,始终没提到两棵树合并时是按什么规则合并,简单的并查集中是随机选取一个作为新树的根节点。而这种随机有可能会降低效率。

img

如上图,此时要合并78,有两种选择:

img

如果把7的父节点设为8,会使树的高度增大,树中每个元素到根节点的路径都变长了。虽然在后续查询时,可以通过路径压缩降低高度,但是这里多条路径耗费时间且是滞后的,我们可以在合并时就进行优化。

如果把8的父节点设为7,就没有这些问题,没有影响其他节点,合并后树的高度也没有增加。这启发我们把简单的树合并到复杂的树上。

也就是按照某种规则决定合并的方向,使得合并后树的高度尽可能小。某种规则也就是(rank),用来描述树的复杂程度,通常可以是树的高度树的节点个数

用一个rank数组记录每个节点对应子树的秩。初始化时,每个节点的rank都是1;合并时,比较两个节点的rank大小,把rank较小的树合并到较大者;更新合并后的rank

这里给出以树的节点个数作为秩时,按秩合并的实现:

1
2
3
4
5
6
7
8
void Union(int x, int y){
int rootx = find(x), rooty = find(y); // 查询x,y各自的根节点rootx,rooty
if(rank[rootx] < rank[rooty]){
swap(rootx, rooty);
}// rootx是rank较大者
fa[rooty] = rootx; // 把rank较小的rooty的父节点设为rootx
rank[rootx] += rank[rooty]; // 更新合并后树的rank
}

以树的高度作为秩也是可行的,需要注意不同高度的树合并后新高度是两者中较大的高度,相同高度的树合并后新高度是原高度+1。
然而考虑到查询时路径压缩会改变树的高度,而且查询时并不会修改rank,所以合并时的rank可能并不是准确的高度值。所以一般用的少,这里就不做具体实现了。

其实不准确的高度值并不会影响合并方向的正确性,此时rank虽然不是准确的高度值,而是子树高度的上界,这个值是有意义的,也可以描述子树的复杂程度。

完整实现

在查询和合并,我们还可以给并查集添加一些其他操作方便实际使用

  • 获取连通分量(connected components)的个数

    连通分量的个数 = 不相交集合的个数 = 集合代表元素的个数,因此只需要求出代表元素的个数即可。而代表元素的特点是它的代表元素是自己。

    1
    2
    3
    4
    5
    6
    7
    int getCC(){
    int cnt = 0;
    for(int i=0;i<fa.size();++i){
    if(fa[i] == i) cnt++;
    }
    return cnt;
    }
  • 跳过冗余边

    在合并操作时,如果两个元素已经在同一个集合中也即两个点已经在同一个连通分量中了,那么再对这两个点进行连接就会形成冗余边。在按秩合并时,自己和自己合并会导致rank翻倍增加。大量的冗余边会导致并查集的效率降低。

    因此,在合并前可以判断一下是否是冗余边,若是则直接结束操作以节省时间。

完整代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
class UFS{
private:
vector<int> fa; // 父指针数组
vector<int> rank; // 秩数组
public:
// 构造函数,初始化
UFS(int n){
fa.resize(n);
for(int i=0;i<n;++i){
fa[i] = i; // 把单个节点的父节点设为自己
}
rank.resize(n, 1); // 初始秩设为1
}

// 查询时路径压缩
int find(int x){
return x == fa[x] ? x : (fa[x] = find(fa[x]));
}
// 按秩合并
bool Union(int x, int y){
int rootx = find(x), rooty = find(y); // 查询x,y各自的根节点rootx,rooty
if(rootx == rooty) return false; // 跳过冗余边
if(rank[rootx] < rank[rooty]){
swap(rootx, rooty);
}// rootx是rank较大者
fa[rooty] = rootx; // 把rank较小的rooty的父节点设为rootx
rank[rootx] += rank[rooty]; // 更新合并后树的rank
return true;
}
// 获取连通分量个数
int getCC(){
int cnt = 0;
for(int i=0;i<fa.size();++i){
if(fa[i] == i) cnt++;
}
return cnt;
}
};

时间复杂度

优化 平均时间复杂度 最坏时间复杂度
无优化
路径压缩
按秩合并
路径压缩+按秩合并

这里α 表示阿克曼函数的反函数,在宇宙可观测的 n 内(例如宇宙中包含的粒子总数),不会超过5

证明非常复杂,感兴趣的可以参考以下论文:

A class of algorithms which require nonlinear time to maintain disjoint sets - ScienceDirect

Worst-case Analysis of Set Union Algorithms

应用

并查集应用十分灵活,通常用于处理与连通性有关的问题。涉及到集合的合并、点的连通等问题时,就可以考虑使用并查集解决。

解决相关问题时,首先需要在问题中抽象出一个,确定图中的点集,确定两点的连通关系如何表示。

基于图可以解决以下问题:

  • 求无向图的连通分量个数
  • 判断无向图中是否有环(求环的个数)、是否有冗余边(求冗余边的条数)
  • 利用对连通性的判断,求kruscal最小生成树

例题

求连通分量个数

839. 相似字符串组 - 力扣(LeetCode) (leetcode-cn.com)

765. 情侣牵手 - 力扣(LeetCode) (leetcode-cn.com)

求最小生成树

778. 水位上升的泳池中游泳 - 力扣(LeetCode) (leetcode-cn.com)

删除冗余边

1579. 保证图可完全遍历 - 力扣(LeetCode) (leetcode-cn.com)