并查集

并查集是用来管理元素分组情况的数据结构。

并查集可以高效的进行如下操作。

查询元素a和元素b是否属于同一组。

合并元素a和元素b所在的组。

并查集不能进行分割操作。

并查集的实现就是三个函数

初始化

合并

查寻

在树形结构中都存在退化的现象，为了让并查集避免退化我们记录了树的高度，在合并的时候我们将高度低的树加入到高度高的树上。

我们还用了路径压缩（好厉害的名字） 其实就是

从图中可以很清晰的看明白。

现在我们来写构造并查集的代码

第一个初始化：

就是将所有的点都是 自己属于一类，与别人没有关系 ，自己的父节点是自己；

接下来是查找函数

查找的是自己最上面的节点是谁，也就是说，自己属于哪一类；

最后我们来附上最牛掰的 合并函数：

好了  到这我们的并查集就基本结束了。

好了感谢自己坚持