1.可以维护整个连通块的信息, 一般都用于维护大小, (需要是环图)
仅仅只是一个环, 才可以用并查集求连通块大小, 如果是一个复杂的图中存在某些环, 只能用tarjan求O(n), 或者用深搜O(n(nm))
🔗
2.并查集不仅能够用于合并集合, 还有一个位于数轴上的作用 => 可以快速找到前/后一个位置的某个未被”使用”过的位置
每当使用完一个位置之后, 就让该点指向前面的点, 这样每一个集合find找到的祖先节点就是合法的位置
🔗
3.并查集还可以维护每一个节点到根节点的距离 (每次更新只更新根节点的d, 然后在路径压缩的时候会传递到所有的子节点上)
有时候为了维护d数组, 还需要额外增加一个cnt数组来表示集合的大小 (在合并集合的时候更新d)
🔗
扩展域并查集与带权并查集的区别:
带权并查集只能描述节点之间的相互关系,扩展域并查集可以描述单个节点的状态
例如奇偶性: 使用带权并查集只能描述节点之间的奇偶性是否相同, 而用扩展域并查集可以描述单个节点是奇还是偶
在写扩展域并查集的时候最好统一形式: 在判断是否成立的时候只需要判断另外的条件是否已经被合并, 然后在合并的时候将所有情况都合并
例如:在奇偶性中, 当奇偶性相同时, 只需要判断两个节点的奇偶是否被合并, 然后在合并的时候将奇与奇合并, 偶与偶合并