并查集： 判断两点之间是否连通 **：将所有的点分组 连通的点分为一组 随着数据的不断输入整个图的连通性也会发生变化那么组的个数也会发生变化 我们所要做的就是对输入的过来的数据判断是否连通 而对于已经连通的我们选择忽略掉 对未连通的进行连通 问题就是我们如何连通 想想有什么样的数据结构是可以把所有的节点更好的组织起来 链表 树 图 那其中对查询和修改的效率最高呢？ 毫无疑问 树 因此考虑将组和节点的关系用树的形式表现出来 这里我们选用数组作为最底层的数据结构 组织方式用parent_link的方式组织起来 举例而言就是如果p是根那么a[p] = p; 寻根的思路： while(a[p]!=p){   p = a[a[p]]; } 最后得出的便是根了 这是算法复杂度的核心 也就是说树越深就所要花的时间就越多 输入的数据不在同一组的时候 我们就要考虑如何融合两颗树 如果两棵树随意谁当爸爸 那么树的深度就与输入数据是否排序 是否随机有很大的关系了 很有可能导致我们建的BST 退化 所以在两个树融合时我们还要考虑所建树的形态的平衡性 很容易想到让深度小的成为深度大的的树的子树 我们首先以一个树的节点总数为依据 if(rootp != rootq){ if(sizep > sizeq) a[rootq] = rootp; sizep += sizeq; } 光这样还是远远不够的 如果一个树足够的扁平那么我们就可以节省很多的搜索时间 理想的状态下就是树的深度为1

在哪里修改呢 while(a[p]!=p){   a[p] = a[a[p]];   p = a[p]; } 只需在寻根是把节点的根提高一个层次 寻根的同时压缩的路径;