并查集理论基础

• 并查集主要有两个功能：将两个元素添加到一个集合中。判断两个元素在不在同一个集合

• 思想：用一个一维数组表示三个元素A，B，C （分别是数字）在同一个集合，即father[A]=B，father[B]=C 表示A与B与C连通了（有向连通图）。但无法也无需知道B连通A，类似树的结构，把root当成分类的标准，当root都相等的时候，说明在同一个集合

• 怎么判断元素联通/元素在同一个集合，只需要递归求得元素的根是否是同一个，

• 怎么表示C也在同一个元素集合里呢？ 只需 father[C] = C，即C的根也为C，所以father数组初始化的时候要 father[i] = i，默认自己指向自己。

• 路径压缩：为了避免在多叉树情况下寻根递归次数过多，将非根节点的所有节点直接指向根节点。只需要在递归的过程中，让 father[u] 接住 递归函数 find(father[u]) 的返回结果。