并查集可以视为连通图的构造，若节点a与b之间连通，则a所在的图与b所在的图就是连通的，即可以合并。 并查集常用于元素分组的问题，用于管理一系列不相交集合。
- 查找
判断两个元素是否在同一个集合中
- 合并
将两个集合合并为一个集合
- 构建数组
构建数组，保存每个元素所在集合的父节点 若保存根节点，则每次发生合并时，需要将集合内的所有元素都更新根节点
- 初始化
初始化时每个元素的父节点为自身
- 查找
查找当前元素所在集合的根节点 只需递归查找当前元素的父节点，当元素的父节点为自身时就是根节点
- 合并
将两个节点所在集合的根节点的父节点置为另一个根节点
- 路径压缩
由于数组保存的是父节点，因此查找一个元素的根节点需要的递归次数为构成的树的高度 树越高，查找越慢，因此有必要优化 所以在每次合并操作时，更新递归查找路径中的元素的父节点为根节点
- 按秩合并
合并操作时应尽可能将高度低的树挂到高度高的树下，这样树的高度变化得最小 因此可以另构建一个数组保存元素的子树的高度 合并时根据树的高度选择最终集合的根节点
- 初始化
构建一维数组，初始化值为自身
- 查找
递归查找当前元素的父节点，直到节点的值为本身
- 合并
给定两个节点合并，查找两个节点的父节点，将其中一个的值改为另一个
- 映射
对于给定的多维数组，可以通过函数映射为一维数组
- 虚拟节点
对于某些特定场景，某些集合本身不属于一个集合，但是可以视为一个集合，可以采用虚拟节点做为集合合并的纽带
当确定了一个题目可以由并查集解答时，采用一下步骤
- 初始化
- 查找合并
遍历给定数组，将连通的节点进行查找合并 对于多维数组，使用函数映射为一维数组
- 分析结果
根据合并结果得出解答结果 例如集合的数量，替换连通集合的元素值等