并查集

简述概括并查集

并查集是一种用来处理不相交集合的数据结构，通过这种数据结构可以很方便的判断两个元素是否属于同一个集合。 并查集的基本操作有两个：

• 并（合并，union）：把两个不相交的集合合并为一个集合
• 查（查找，find）：查找元素所在的集合

另外，这种结构很难以较低的时间复杂度实现集合的分离操作，因此并查集一般不用来处理分离。

上图中，ABCD为一个集合，EFG为另一个集合。

并查集的实现

实现思路：用一个数组来存储每个元素的父节点，一开始，每个元素的父节点都是它自己，即每个元素自成一个集合，每个集合的代表元素就是这个集合的根节点。

然后，每次合并两个集合时，只需要将其中一个集合的根节点的父节点指向另一个集合的根节点即可。

合并A-B，将B的父节点指向A

合并B-C，将C的父节点指向B

遍历完所有的合并操作后，就得到了一个并查集。对应的树结构如下：