## <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极大，设计一种可行的并行计算方案