并查集

并查集维护的是不断合并的集合划分，而不是支持任意拆分的通用集合容器。每个等价类由一棵父指针树表示，根是代表元；合并只需连接两个根，查找则沿父指针到根。路径压缩缩短查询经过的链，让以后访问几乎直接到达根；按秩或大小合并则避免小树吞并大树。两种启发式共同给出近乎常数的摊还复杂度，但单次操作仍可比常数长。

初始集合为 $\{1\},\{2\},\{3\},\{4\}$，约定等大时保留第一个参数所在块的根。前两次合并 $\mathrm{union}(1,2)$、$\mathrm{union}(3,4)$ 后，父链接为 $2\to 1$、$4\to 3$，两根大小均为 $2$。执行 $\mathrm{union}(2,4)$ 先查得根 $1,3$，再令 $3\to 1$，根 $1$ 的大小变为 $4$。

此时 find(4) 沿 $4\to 3\to 1$ 查到代表元，然后把 $4$ 直接连接到 $1$。改变的是表示中的路径，抽象划分完全不变。随后再次 union(2,4) 时，两端根都为 $1$，应立即结束；若仍把大小相加，就会错误地把同一块重复计数。

这个父指针森林不是原图的路径证书。上例中合并的是元素2和4，表示却新增了父指针 $3\to 1$；这条父指针不必是输入图的一条边。Kruskal 中若 find(u)!=find(v)，就加入原图的边并合并两分量；否则该边会成环。若还要输出原图路径，必须另存所选图边。代表元的具体编号没有持久语义，合并后可能改变，不能依赖“根一定是最小元素”或把根编号当作集合身份，除非额外维护。

路径压缩会修改结构，因此需要撤销时通常改用可回滚并查集理路可回滚并查集rollback DSU · undoable union-find把每次合并修改压栈，以快照栈长度为边界撤销最近更新的并查集。的按秩/大小合并与操作栈；它牺牲路径压缩，换取可恢复历史。

严格持久化还要定义版本分叉后的共享与更新成本，并行版本则要处理并发 find/union 的竞争与原子性；二者都不能直接套用顺序实现及其摊还证明。离线动态连通性理路离线动态连通offline dynamic connectivity把边的活跃时间区间分配给时间线段树，并用可回滚并查集回答离线连通查询。再把边的活跃区间分配到时间结构上，标准 DSU 本身仍不支持拆分或删除。

只做按大小合并而不压缩时，每当某节点深度增加，其所在块的大小至少翻倍，所以深度至多 $\lfloor {\log }_{2}n\rfloor$。这给出单次查找的对数界，也解释为什么“把小根挂到大根”是必要规则。路径压缩的更强总界则需要独立的摊还证明。

并查集用于最小生成树、图像分割、等价约束和离线查询；Karger 收缩算法理路Karger 随机收缩算法Karger contraction algorithm · random contraction min-cut反复均匀收缩随机边，以固定最小割存活概率分析无向全局最小割。也反复合并随机边端点，但其目标是随机保持一个最小割，成功概率来自收缩过程，而不是 DSU 的复杂度保证。共享 union 操作不意味着两种算法解决同一问题。