You can not select more than 25 topics Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.

44 lines
2.2 KiB

This file contains invisible Unicode characters!

This file contains invisible Unicode characters that may be processed differently from what appears below. If your use case is intentional and legitimate, you can safely ignore this warning. Use the Escape button to reveal hidden characters.

This file contains ambiguous Unicode characters that may be confused with others in your current locale. If your use case is intentional and legitimate, you can safely ignore this warning. Use the Escape button to highlight these characters.

## <center>并查集</center>
&emsp;&emsp;在计算机科学中并查集英文Disjoint-set data structure直译为不交集数据结构是一种数据结构用于处理一些不交集Disjoint sets一系列没有重复元素的集合的合并及查询问题。
&emsp;&emsp;解决两大块区域的合并问题,常用在图等领域中。
<br />
### 并查集的模型
* 有若干个样本a、b、c、d…类型假设是V
* 在并查集中一开始认为每个样本都在单独的集合里
* 用户可以在任何时候调用如下两个方法:
boolean isSameSet(V x, V y) : 查询样本x和样本y是否属于一个集合
void union(V x, V y) : 把x和y各自所在集合的所有样本合并成一个集合
* isSameSet和union方法的代价越低越好
### 合并
&emsp;&emsp;合并操作是将两个并查集指向同一个代表节点而不是将两个集合放到一个新的集合中。可以使用map或者数组实现合并操作。数组实现的合并操作在常数项时间复杂度更有优势。小集合挂在大集合的下面可以减少路径压缩操作。
<br />
### 查询
&emsp;&emsp;从下往上递归查找代表节点并处理路径压缩。可以借助Stack或者数组处理路径压缩。
<br />
### 并查集的特点
* 每个节点都有一条往上指的指针
* 节点a往上找到的头节点叫做a所在集合的代表节点
* 查询x和y是否属于同一个集合就是看看找到的代表节点是不是一个
* 把x和y各自所在集合的所有点合并成一个集合只需要小集合的代表点挂在大集合的代表点的下方
* 如果方法调用很频繁那么单次调用的时间复杂度为O(1)
LeetCode547 Friend Circles
使用并查集合并,最后返回子集的个数
LeetCode200 Number of Islands
给定一个二维数组matrix里面的值不是1就是0上、下、左、右相邻的1认为是一片岛返回matrix中岛的数量。
合并、查询,暴力循环(上下左右递归感染)、使用map实现并查集、使用数组实现并查集
LeetCode305 Number of Islands II
岛问题扩展
如果matrix极大设计一种可行的并行计算方案