算法1中的并查集部分

算法1之并查集

并查集：一种基于树形结构的数据存储方式，在算法实现中主要涉及将两个不同的集合进行快速合并以及快速查找或确定某个元素是否存在于该特定集合中的两种基本操作。“并查集”的名称由三个关键字（并、查、集）完整描述了这一算法的基本功能特性，在实际应用中常采用森林结构来实现这一算法

一、并查集思想

1.1 算法思想

假设将集合中的每个元素视为树上的独立节点，则问题转化为判断这两个元素所在的树是否拥有相同的根节点

1.2 路径压缩

同一个树体上分布着多支不同的主枝，在各个层次上分布着不同类型的叶单元（即我们所说的元素）。在搜索过程中将所有属于x且位于root子树中的叶子结点的父亲字段直接指向root以提高找到某片叶子所属根系速度，并将其这种方法命名为路径压缩算法

采用路径压缩优化技术后
平均时间复杂度等价于 Ackerman 函数的反函数
在实际应用中大致上被认为近似为常数

1.3 问题描述

以亲戚为例来说的话，则会发现：某个人可能是你的远亲——他的祖父或许是你的曾祖父；而他的妻子则有可能是曾祖母或祖母等不同辈分的角色；他们的子女、孙子女等亲属关系也各有不同

借助亲属谱系图,人们可以相对简便地识别出两人是否为亲戚.然而,当两个人的最近公共祖先相隔好几代导致亲属关系网络变得极为复杂时,检验两人