【算法】并查集—板子与简单例题

原理

并查集是一种管理元素集合的数据结构，将某一种类型的元素归纳到一个集合中，从而实现合并与查找的两个功能。

假设一个数组，其中每个元素的父亲都是其自身，比如A的父节点是其自身，B的父节点是其自身，我们通过一些操作，把A的父节点变为B，这样就是并查集中合并的操作，我们通过寻找A的父节点找出B，这就是并查集的查找。

实现

• 初始化：首先需要初始化每个元素的父节点，也就是其自身。
  

• 查找：当前元素的父节点不是其自身的话，那么我们就接着找他父节点的父节点，直到   父节点的值等于其自身停止查找。

• 合并：就是将一个元素的父节点的值修改为另一元素，实现元素合并到同一集合。值得注意的是，我们在合并的时候，合并的是每个元素的父节点，而非其自身，这样就可以实现集合与集合的合并。

• 路径压缩：仔细思考一下，我们在查找的时候，如果该元素的父节点不是其自身的话，每次都要查找，那么在某种情况下，这棵树就会退化成一个链表，从而大大增加时间复杂度，那我们这个时候就需要压缩路径，在查找的同时，把该元素的父节点修改为树的根节点。如下图。

这样查找的代码就可以优化为如下：

查找（路径压缩）

那么就可以看一道简单的并查集例题

示例

AC代码