并查集

Vision271 · 2022-07-11 22:18:33 · 个人记录

概述

• 并查集通过家长制，维护每个点所在的集合。

操作

• 并查集支持合并和查询操作。

• 和其他可合并的数据结构一样，它也可以启发式合并，但由于特殊的树形结构，对其有效的实质上是按秩（深度）合并。

• 不过容易证明深度和 siz 是对数关系，所以启发式合并只是常数稍大。

复杂度分析

• 只按秩合并或只路径压缩的均摊复杂度均为 O(\log n)，当然仅在特殊构造数据下可以卡满。

• 两者都有的话，均摊复杂度为单次 O(\alpha(n))。该函数为反阿克曼函数，\alpha(n) 即使得 A_k(x)>n 的最小 x。

• 反阿克曼函数的增长非常缓慢，远低于对数函数，实际使用中可以视作 O(\approx3)，这个结论至少在 n=10^6 时仍然成立。

实现原理

• 查询：

  • 若有父亲则回溯到父亲，直到找到族长为止。

  • 路径压缩优化：将回溯过程中访问到的所有点的父亲都改为族长。路径被压缩了，构成一个菊花图。

• 合并：

  • 首先判断是否同集合，同集合最好不要合并（不按秩合并的话无所谓）。

  • 不同集合则让一个族长认另一个族长为父亲。

  • 按秩合并优化：总是让 rnk 小的族长当儿子。

    • 这里 rnk 可以使用 dep,siz(\log_2siz\approx dep) 或随机权值 pri。

    • 前两者的证明见 OI Wiki，随机权值的理由是随机排列的期望最长上升子序列长度为 O(\log)。

• 需要提前把所有点都初始化成认自己作父。这里给出一种路径压缩+随机秩的实现。

namespace ufs{
    int FA[maxn],rnk[maxn];
    il void init(){iota(FA+1,FA+n+1,1); For(i,1,n) rnk[i]=_rand(); return;}
    il int find(int x){return x==FA[x]?x:FA[x]=find(FA[x]);}
    il void merge(int u,int v){
        static int fau,fav;
        fau=find(u),fav=find(v);
        if(fau==fav) return;
        if(rnk[fau]<rnk[fav]) swap(fau,fav);
        FA[fav]=fau; return;
    }
} 

• 非递归查找自然是可行的，但现代编译器一般会自动递归展开乃至循环展开（看情况，这个效果时好时坏），故真的需要时...算了，写一个放在这吧。

il int find(int x){
    static int fa,temp; fa=x;
    while(fa!=FA[fa]) fa=FA[fa];
    while(x!=fa){
        temp=FA[x];
        FA[x]=fa;
        x=temp;
    }
    return;
}

扩展

• 并查集可以实现可撤销化和可持久化。可追溯化这种东西还是太刺激了，得靠 LCT...

• 所谓可撤销化，即可以以和修改操作同阶的复杂度撤销最后一次操作。一般利用数据结构本身的性质。

• 所谓可持久化，即可以 O(1) 地回退到任意一次操作后的状态。一般依赖主席树实现。

• 所谓可追溯化，即可以在可接受的时间内撤销操作序列中的任何一个操作。一般只有 LCT 能支持。

可撤销化

• 记录发生了怎样的修改，改回去。一般来说是以和操作对称的顺序来逆向修改 rnk 和 fa。

• 为了实现的方便，常常使用随机 rnk 合并，因为其不用撤销，于是只需要维护谁要认自己作 fa 即可。另外这也有利于卡空间（一般需要可撤销化并查集的题目都是线段树分治之类的，随机 rnk 可以用 short）。

可持久化

• 用主席树实现可持久化数组，作为 fa。也建议使用随机 rnk，因为不用修改...还省下一半的版本量。

• 主要是要在主席树节点编号和实际节点编号之间不断跳来跳去，因为 fa 必须是实际节点（否则一改版本，某个节点的编号一变，旧有的 fa 信息就崩了）。

与分块结合

• 我们要知道，并查集是有 siz 的。

• 嗯？siz 不是 2^{rnk} 的替代品吗？

• 你说得对，但是：

  • 考虑一种“将区间内的所有 x 都改为 y”的修改操作。

  • 显然这一操作没法用线段树维护（至少我想不到），考虑分块；发现给整块打了 tag 之后没法快速计算一些信息，比如区间和或者区间积，核心原因在于我们不知道到底发生了什么。

  • 换言之，核心原因在于我们不知道块内到底有多少个 x。注意到这种修改操作是近似不撤销的——我是指，不同的集合会合并，但相同的集合的分裂次数最多 O(n) 次左右；又注意到，我们只关心数量。

  • 并查集！并查集！块内维护一个并查集，再另外开一个 u_set 记录存在哪些数字及其代表元素（其实随便哪个都可以），问题解决，O(n\sqrt{n}\alpha)，参见 \text{P8576 「DTOI-2」星之界}。

  • 注意到散块的并查集可能并不好维护...解决办法：暴力重构！卡常？额...自求多福啦...

• 这一做法可以推广到 \text{P4119 [Ynoi2018] 未来日记}，具体来说：

  • 首先我们在分块那边谈过单点修改的区间第 k 小。显然，这种 x 全部变成 y 是符合单点修改的形式的，使劲乱搞可以使得前缀和数组 s 在 O(\sqrt{n}) 时间内维护好。

  • 非常卡常而且也不好写...蚌，等我以后准备创数据结构了再说吧。

• 还有 \text{P8360 [SNOI2022] 军队}，但是这道题我被卡常了！蚌。另外这道题引出了并查集的另一个扩展，见下。

lazy tag

• 没想到吧！我并查集也能打 tag！

• 考虑并查集的树形结构，我们直接在根处打一个 lazy tag，然后暴力重构的时候跑一下 dfs（当然并查集只有反边，我们可能得把拓扑序拉下来）。

• 多一只 \log？不，路径压缩仍然成立。考虑使用非递归 find，将访问到的所有节点（除了 rt）存入栈中，按深度单增的顺序下推 lz，然后改 FA 为 rt。当然因为只有反边，事实上是把 lz 拉下来。

• 怎么 merge？好问题，不妨假设已经判断 fau 当新根，那么 lz_{fav}-=lz_{fau}，其余不变。

• 发现复杂度并没有升高，仍然是 O(\alpha)，妙啊！就是有点难写。