0%

并查集原理与应用

并查集是一种树形数据结构,用来处理不交集(Disjoint Sets)的合并、查询问题。

并查集有两个操作,叫做联合-查找算法(Union-find Algorithm),其实可以理解为一个查询操作还有一个合并操作。就像C++的string有find和strcat一样。

并查集结构

前面说了并查集是树形结构,那么我们可以在脑海中构建一个多叉树来思考一下。

比如一个班级有50个学生,他们被分成了几个大组,每个大组有一个同学是大组长,然后每个大组分成几个小组,每个小组有一个小组长。

这样他们就构成了几棵树,每棵树代表一个大组,这个结构很像公司的组织架构。

我们可以把这50个学生序号编为0-49,当作一个大小为50的数组。

1
int a[50];

那么数组里面存放什么呢?数组里存的是每个学生自己直属上级的序号,如果没有上级就是自己的序号。

查找算法

有了并查集这样的数据结构,我们就很容易区分任意两个同学a和b是不是在同一个大组:

告诉我a和b的序号,就到数组中分别找他们的上级,上级的上级,一直找到最上级,也就是上级是自己的时候返回,最后比较他们的上级是不是同一个人即可。

查找某位同学最上级的函数这么写:

1
2
3
4
5
6
7
8
9
int a[50];
//查找x的最上级
int find(int x)
{
int i = x;
while(a[i] != i)
i = a[i];
return i;
}

很显然,如果组织架构很大,也就是树很高的时候这样查找会比较慢,下面会使用路径压缩来优化这个过程。

路径压缩

路径压缩可以通俗地理解为每个学生直接记住自己的最高上级,很显然这样比记住直属上级然后一级一级查找要快很多。

我们可以把路径压缩放到查找函数中进行,也就是找到某个学生的最上级的之后,让这条路径上所有人都记住自己的最上级。这样虽然相当于查找了两遍,但是在之后查找的时候基本上都可以直接找到最上级,可以节省很多时间。

代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
int a[50];
int find(int x)
{
//和上面一样 先找到最上级i
int i=x;
while (a[i] != i)
i = a[i];

//路径压缩
//就是让刚才那条路径的人都记住i
int j = x;
int tmp;
while(j != i)
{
tmp = a[j];
a[j] = i;
j = tmp;
}
return i ;
}

联合算法

联合算法就是把两个大组合为一个大组,很简单,比如A、B两个大组,让A组的大组长成为AB合并后的新大组长即可(即A成为B的上级),当然让B组大组长当也可以。

联合算法需要传两个参数,分别是两个组的组员序号,比如x和y。

代码如下:

1
2
3
4
5
6
7
void union(int x,int y)
{
int A=find(x);//找到x最上级
int B=find(y);//找到y最上级
if(A!=B)
a[B]=A;//让A成为B的上级
}

这样一来,A、B两个大组就联合成一个大组了。

并查集应用

并查集很适合用在连通性问题中,尤其是图类问题。

比如图上有很多点,点与点之间有路径或者没有路径,然后问你图是不是连通的,如果不是,需要再连几条线才能连通,或者问你图里有几个连通分量(分支)。

这些问题都可以转化为并查集问题,比如 HDU 1232 畅通工程

初始化的时候可以把每个点都当作一个小组,每个点是自己的组长,然后如果两点之间有线就union联合起来。最终遍历一下数组,就知道有几个连通分量了。