并查集

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

初始集合为 $\{1\},\{2\},\{3\},\{4\}$。执行 $\mathrm{union}(1,2)$、$\mathrm{union}(3,4)$、$\mathrm{union}(2,4)$ 后四个元素同属一类；一次 $\mathrm{find}(1)$ 可把沿途节点直接连到最终根。

Kruskal 中若 find(u)!=find(v)，就加入边并合并两分量；否则该边会成环。代表元的具体编号没有持久语义，合并后可能改变，不能依赖“根一定是最小元素”或把根编号当作集合身份，除非额外维护。路径压缩会修改结构，因此需要撤销时通常改用可回滚并查集公理库可回滚并查集rollback DSU · undoable union-find把每次合并修改压栈，以快照栈长度为边界撤销最近更新的并查集。的按秩/大小合并与操作栈；它牺牲路径压缩，换取可恢复历史。严格持久化还要定义版本分叉后的共享与更新成本，并行版本则要处理并发 find/union 的竞争与原子性；二者都不能直接套用顺序实现及其摊还证明。离线动态连通性公理库离线动态连通offline dynamic connectivity把边的活跃时间区间分配给时间线段树，并用可回滚并查集回答离线连通查询。再把边的活跃区间分配到时间结构上，标准 DSU 本身仍不支持拆分或删除。

集合划分公理库集合划分Set partition把集合表示为两两不交非空块且其并为全体的块族。给出抽象语义，父指针树公理库树Tree连通且无圈的有限简单无向图，也就是任意两点之间只有一条简单路径的图。给出表示，摊还分析公理库摊还分析Amortized analysis对操作序列的总成本作上界，而非逐次最坏成本。说明一串操作的总成本。并查集用于最小生成树、图像分割、等价约束和离线查询；Karger 收缩算法公理库Karger 随机收缩算法Karger contraction algorithm · random contraction min-cut反复均匀收缩随机边，以固定最小割存活概率分析无向全局最小割。也反复合并随机边端点，但其目标是随机保持一个最小割，成功概率来自收缩过程，而不是 DSU 的复杂度保证。共享 union 操作不意味着两种算法解决同一问题。