并查集原理与应用

发表于

并查集是一种树形数据结构，用来处理不交集（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联合起来。最终遍历一下数组，就知道有几个连通分量了。