一、并查集的概念
在一些场景中，需要将n个不同元素划分为一些不相交的集合。开始时，每个元素各成一个元素，然后按一定的规律将属于同一组的元素合并。这个过程中需要反复用到查询一个元素是否属于某个集合的算法。适合用于这种场景的数据结构是并查集（Union-Find Set）！
并查集的底层结构本质上是一片森林（多棵树的集合）
比如，我现在有九个数据元素，给他们编号0~8：
按照某种需求，这些数据被分组合并为：
按照其他需求，这些树可以继续合并下去…
而这个森林，可以用一个数组记录下来元素的关系！
我们可以规定并查集用数组下标代表每个元素，数组内容代表元素之间的关系：
- 数组下标代表元素编号
- 如果数组内容为负整数，代表这个下标是根，绝对值表示它这棵树的元素个数
- 如果数组内容为非负整数，代表这个下标不是根，数组内容是它的父亲在数组中的下标
比如，上面的森林例子，用并查集数组表示，就是：
如果元素的数据类型不能直接作为数组下标，只要在实现中用std::map之类的结构，建立元素到下标的映射关系，就能解决了！
通过并查集的特点，可以看出并查集一般能解决：
- 查找元素属于哪个集合：沿着数组一直找到元素为负数，就是根
- 查看两个元素是否属于一个集合：看看这两个元素的根是否相同
- 将两个集合归并为一个集合：假如要将下标a的树合并到下标b的树中，arr[b] += arr[a]，arr[a] = b即可，即令1成为0的一个孩子
- 统计集合的个数：统计数组中元素为负数的个数
二、并查集的实现
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 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 |
|
测试：
三、算法题中的应用
并查集的特点在某些算法题中很有用：
- 省份数量
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 46 47 |
|
- 等式方程的可满足性
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 46 47 48 49 |
|
总结
到此这篇关于C++并查集的原理与使用方法的文章就介绍到这了
