形式陈述

并查集维护一个动态划分，支持 make-set(x)、find(x) 返回所在块代表元、union(x,y) 合并两块。森林实现让每个集合是一棵根树；按秩或大小合并把浅树挂到深树，路径压缩在查找时把经过节点直接连到根。对 $m$$m$ 次操作和 $n$$n$ 个元素，两种优化合用的总时间为 $O(m\alpha(n))$$O(m\alpha (n))$，其中 $\alpha$$\alpha$ 是反 Ackermann 函数；这是摊还界。

直觉

每个等价类选一个根作代表。合并只需连接两个根，查找则沿父指针到根；路径压缩让以后访问几乎直接到达。

例子与边界

Kruskal 中若 find(u)!=find(v)，加入边并合并两分量；否则该边会成环。代表元本身没有持久语义，合并后可能改变，应用不应把根编号当作集合身份。路径压缩会修改结构，因此严格持久化或并行版本需额外设计。$O(\alpha(n))$$O(\alpha (n))$ 不是单次最坏常数，而是在操作序列上的摊还界；只有按秩不压缩可给 $O(\log n)$$O(\log n)$ 单次上界。标准 DSU 不支持拆分或删除。

推论与应用

并查集用于动态图连通、最小生成树、图像分割、等价约束和离线查询，是摊还分析最典型的数据结构之一。

参考资料

• Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein, Introduction to Algorithms, 4th ed., MIT Press, 2022，Parts I–VI。
• Robert E. Tarjan, Data Structures and Network Algorithms, SIAM, 1983，Chs. 1–6。