并查集

绝活（套娃启动） https://blog.csdn.net/qq_41593380/article/details/81146850

接下来试图用最简单的语言描述目前对并查集的理解。

前提：

1. 并查集是一个算法，处理一组集合；
2. 并查集可以查找两元素是否在同一集合；
3. 并查集可以合并多个集合。（可以理解为，在要合并的多个集合中每次合并两个，最终只剩一个）

原理：

1. 并查集中所有集合视作森林，单个集合视作树；
2. 树最多是双层的；
3. 通过树根节点的选举实现集合的合并。

实现：

1. 可以使用数组简单地实现并查集：下标为元素编号（信息），存储的内容为当前元素（在树上）的父元素；
2. 指向自己的元素为树根；
3. 通过元素存储的父元素信息判断两个元素是否属于同一集合；
4. 树的合并需要对某一集合的所有元素（包括树根）的父元素进行修改；
5. 初始化并查集数据的时候就应该把所有的树结构缩减为双层的。