[集训Day3]并查集

并查集被很多OIer认为是最简洁而优雅的数据结构之一,主要用于解决一些元素分组的问题。它管理一系列不相交的集合,并支持两种操作:

合并(Union):把两个不相交的集合合并为一个集合。
查询(Find):查询两个元素是否在同一个集合中。

当然,这样的定义未免太过学术化,看完后恐怕不太能理解它具体有什么用。所以我们先来看看并查集最直接的一个应用场景:亲戚问题。

(洛谷P1551)亲戚
题目背景
若某个家族人员过于庞大,要判断两个是否是亲戚,确实还很不容易,现在给出某个亲戚关系图,求任意给出的两个人是否具有亲戚关系。

题目描述
规定:xxyy是亲戚,yyzz是亲戚,那么xxzz也是亲戚。如果x,yx,y是亲戚,那么xx的亲戚都是yy的亲戚,yy的亲戚也都是xx的亲戚。

输入格式
第一行:三个整数n,m,pn,m,p,(n5000,m5000,p5000n\le 5000,m\le 5000,p\le 5000),分别表示有nn个人,mm个亲戚关系,询问pp对亲戚关系。
以下mm行:每行两个数MiMj1MiMjNM_i,M_j,1\le M_i,M_j\le N,表示MiM_iMjM_j具有亲戚关系。
接下来pp行:每行两个数PiP_iPjP_j,询问PiP_iPjP_j是否具有亲戚关系。

输出格式
PP行,每行一个’Yes’或’No’。表示第ii个询问的答案为"具有"或"不具有"亲戚关系。

这其实是一个很有现实意义的问题。我们可以建立模型,把所有人划分到若干个不相交的集合中,每个集合里的人彼此是亲戚。为了判断两个人是否为亲戚,只需看它们是否属于同一个集合即可。因此,这里就可以考虑用并查集进行维护了。

并查集的创建与初始化

一个并查集的元素需要有自己的编号用来代表自己,还需要一个存储一个编号指向父节点,我们可以将这个问题转化到一个数组内,数组的下标就是自己的编号,这个下标的值就是父节点的下标,所以我们一般使用数组来维护并查集:

1
int fa[MAXN]; 

当然,这个数组里是没有值的,也就是还没有指向自己的父节点,所以我们需要初始化这个数组。由于我们一开始还没有并查集里面各个元素的具体指向,所以我们将并查集指向自己,在数组里就是,每个元素对应的值就是自己的下标。

1
2
3
4
void init(int n){
for(int i = 1;i <= n;i++)
fa[i] = i;
}

寻找元素根节点

我们可以很简单地用递归的方式寻找根节点:一层一层地访问父节点,直到根节点(根节点的标志就是父节点是元素本身),要判断两个元素是否属于一个跟节点,只需要判断它们的根节点是否相同即可。

1
2
3
4
int find(int x){
if(fa[x] == x) return x;//判读是否是根节点
else return find(fa[x]);//递归父节点
}

判读是否是一个集合:

1
2
3
if(find(a) == find(b)){
//...
}

并查集的合并

假设我们有一个并查集如图需要合并:

并查集

这张图的意思是,2指向1,1,3都指向自己,转换到数组可以看做fa[1] = 1,fa[2] = 1,fa[3] = 3

只需要将前者根节点指向后者的根节点就行了。

1
2
3
void merge(int a,int b){
fa[find(a)] = find(b);
}

效果如图:

合并后的效果

路径压缩

最简单的并查集效率是很低的,如果元素到根节点的距离很远,则需要递归的次数很多。

为了解决这个问题,我们可以使用路径压缩来尽量减少元素到根节点的距离。简单来说,就是将每个节点的父节点设为根节点就好了。

上代码:

1
2
3
4
5
6
7
int find(int x){
if(x == fa[x]) return x;
else{
fa[x] = find(fa[x]);//将父节点设为递归找到的根节点
return fa[x];
}
}

此代码可以简写为一行(三元运算):

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

并查集的应用

我们先给出亲戚问题的AC代码:

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
#include <bits/stdc++.h>
#define MAXN 5003
using namespace std;
int fa[MAXN];

void init(int n){
for(int i = 1;i <= n;i++)
fa[i] = i;
}

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

void merge(int a,int b){
fa[find(a)] = find(b);
}

int main(){
int n,m,p,x,y;
cin>>n>>m>>p;
init(n);
while(m){
cin>>x>>y;
merge(x,y);
m--;
}
while(p){
cin>>x>>y;
cout<<((find(x) == find (y))?"Yes":"No")<<endl;
p--;
}
return 0;
}
文章作者: Tim
文章链接: http://itstim.xyz/%E9%9B%86%E8%AE%ADDay3-%E5%B9%B6%E6%9F%A5%E9%9B%86/
版权声明: 本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 Tim's Blog
支付宝恰饭打赏
微信恰饭打赏