InTheBloodHorse

数据结构与算法(8) 并查集

字数统计: 1k阅读时长: 3 min
2018/12/31 Share

什么是并查集?

并查集我应该在今年上半年的时候,就写到过,那时候对并查集没有概念,只知道,并查集的问题可以用DFS解决,所以在接下来的日子里,几乎把并查集晾在一边了,只知道有个算法叫,并查集,就这样。(其实就是我看了博客,资料,模版,我看不懂,所以就选择逃避了)今天无意间看到一篇写并查集的,虽然没有牵涉到ACM,但是豁然开朗,我似乎懂这个叫并查集的算法了。
下面是对并查集的官方解释
并查集是一种树型的数据结构,用于处理一些不相交集合(Disjoint Sets)的合并及查询问题。常常在使用中以森林来表示。并查集其中一个典型应用就是在无向图中判断任意两个顶点是否连通。
或者说 集合中的’并’操作,以及查询操作。

设计思想

本文对并查集每个元素初始化的方法与目前流行模版的初始化不同。我更喜欢给每个元素初始化为-1,用数组来描述树,每个元素代表其父节点的坐标,所以当元素的值为-1的时候,代表是他在这棵树里,是根节点,因为他没有父节点,但是他可能有儿子节点。
这是初始情况,代表十个元素都没有关系
TIM截图20181231192021.jpg
现在merge(1,5),代表合并元素1和元素5,使1,5联通,得到如下结果
TIM截图20181231192622.jpg
我们可以发现坐标为5的元素的值变成了1,因为他的父亲节点是1。
我们可以再试着merge(5,6)
可以得到如下结果
TIM截图20181231193012.jpg
我们可以发现坐标为6的元素的值变成了5,因为元素5,6在合并前并不在一个集合内,合并后,元素6指向5,所以现在1,5,6在同一个集合内。但是我们提到过,并查集是为了解决无向图内的连通问题,所以并不在乎方向,那么6指向1也是没关系的,因为6指向1的结果也是1,5,6在同一个集合,变化是在树由之前的高为3变成了高为2,在查询上会快很多,所以在任何一次合并操作的时候,都可以指向 “目标树”的根节点,这样会减少树高。所以我们可以做出较为优的结构。如图
TIM截图20181231193648.jpg
这个操作也被称为路径压缩。

关于查找

其实查找就是一个找根节点的过程。经过我们的路径压缩,查找会快很多。下图任意给出数组,和集合。(部分未使用路径压缩,为了演示~)
TIM截图20181231194208.jpg
要查找4在哪个集合的话,路径如下 4->3->7->6->1。
现在查找8在哪个集合,路径如下 8->7->6->1。
最终结果也为1所以,只要一个集合内,找到的根节点,必定相同,假如根节点不同,则代表可以合并,否则就没何必的必要了。

并查集能做什么?

在这里,我选一道并查集中的水题hdu1213
具体看题解

路径压缩

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
39
40
41
42
43
44
45
#include<bits/stdc++.h>
using namespace std;
int a[1000005];

int find_root(int x){
int root = x;
while(a[root]!=root){
root = a[root];
}
int t;
// 路径压缩
while (root != x)
{
t = a[x];
a[x] = root;
x = t;
}
return x;
}

void merge(int x,int y){
int father_x = find_root(x);
int father_y = find_root(y);
if(father_x == father_y) return;
a[father_y] = father_x;

}

int main()
{
int n,m,k;
scanf("%d %d %d",&n,&m,&k);
int l,r;
for(int i=0;i<=n;i++) a[i]=i;
for(int i=0;i<m;i++){
scanf("%d %d",&l,&r);
merge(l,r);
}
for(int i=0;i<k;i++){
scanf("%d %d",&l,&r);
if(find_root(l)==find_root(r)){
printf("YES\n");
}else printf("NO\n");
}
}

原文作者:InTheBloodHorse

原文链接:http://pyking.cn/2018/12/31/数据结构与算法-8-并查集/

发表日期:December 31st 2018, 6:48:13 pm

更新日期:March 25th 2019, 5:39:06 pm

版权声明:Have a fun

CATALOG
  1. 1. 什么是并查集?
  2. 2. 设计思想
  3. 3. 关于查找
  4. 4. 并查集能做什么?
  5. 5. 路径压缩