不断加入无向边后，怎样判断两个顶点是否已经连通？每次重新遍历图能回答问题，但重复处理了大量已经建立的连通关系。并查集只保存连通分量划分。加入一条边时，合并两个端点所在集合即可，不必保留分量内部所有边。

这种压缩也限定了能力。并查集可以证明两个顶点属于同一集合，却不能直接返回连接路径；删去一条边后，也无法仅凭旧划分判断分量是否拆开。本篇只处理固定顶点集合上的合并与连通查询，不把它当成完全动态连通性算法。

森林表示的是什么

初始化输入n个顶点，编号0到n−1，各自构成一个集合。每个顶点保存一个parent指针，根指向自己；沿parent走到的根是当前代表元。根编号只代表集合身份，不承诺是集合最小编号，合并后也可能改变。

接口 语义
DSU(n) n非负；负数抛ValueError
find(x) 返回当前代表元；编号越界含负数抛IndexError
union(a,b) 合并不同集合时返回True，原已连通返回False
connected(a,b) 比较代表元，返回是否同属一组

逻辑不变量是parent边组成森林，且一棵树恰好对应一个集合。初始化显然满足。union先找到两根，若不同，只把其中一个根连向另一个根，不可能形成环：原来两棵树互不相交。合并后的可达根相同，其他树不变，因此划分恰好完成一次集合合并。

把根连到非根也可能保持集合语义，但会使后面的高度证明失去前提。实现必须先find再链接，不能把用户传入的两个顶点直接当作根。

rank为何不是当前高度

朴素合并若总让旧根指向新顶点，会得到长链。按秩合并给每个根一个rank，初始0；不同秩时小秩根指向大秩根，相同秩时选一个为新根，只把新根的秩加1。没有路径压缩时，秩等于按该规则构造出来的高度；引入压缩后，它成为历史高度的上界。

一个秩r的根所在集合至少含2^r个顶点。初始r=0时有一个顶点；秩只在两个秩r−1根合并时增长，而两组互不相交，大小至少相加为2^r。由此r≤⌊log₂n⌋。父边上的秩严格增加：不同秩合并显然成立，同秩合并后父根恰多1。

这给出单次find最坏O(log(n+1))的直接界，却还没有证明逆Ackermann摊还界。不能把“树高度小”换一种说法就当作完整的序列分析。

压缩改指针，不改集合

完整路径压缩先沿parent找到根，再走原路径，把每个访问到的非根节点直接连到根。第二遍改指针前要保存原父节点，否则无法继续沿原路径前进。根没变，因此集合划分没变；新父亲原本就是祖先，秩严格更大，森林也不会出现环。

1
2
3
4
压缩前: x -> a -> b -> r
压缩后: x ------> r
        a ------> r
        b ------> r

已经扁平的路径以后访问会更短，但其他路径和未来合并仍可能增加访问成本。rank无需重新计算，更不能压缩后因为高度变小就把rank降低；那会破坏前面按历史合并规模建立的单调秩分析。rank不是查询输出，维护它的目的也不是实时显示树形。

极慢增长仍不是常数

MIT 6.046讲义给出的定理是：按秩合并与路径压缩共同使用，若m次操作中包含n次MAKE-SET，且m≥n，总时间为O(m α(n))。α是与讲义定义相配的逆Ackermann函数；它无界增长，只是非常缓慢。该保证是确定性摊还界，没有对随机输入取期望。

本实现构造器一次完成n个单点集合，后续执行q次union/find/connected。connected含两个find，union也只增加常数次find和链接，因此可保守写总时间O((n+q)α(n))，n≥1；n=0时只有初始化合法，访问编号会被拒绝。初始化本身Θ(n)，额外数组空间Θ(n)，两遍find仅用常数个临时变量。

逆Ackermann界的完整证明需要把秩划分成增长极快的层级，分别计数跨层与同层父指针推进；本篇只引用该定理，不声称上面的2^r引理已经完成证明。作为可独立核对的较弱结论，父秩严格增加且秩不超过log₂n，已经给出了O(log(n+1))单次上界。两种证据应分开阅读。

构造一棵尚未压缩的平衡合并树，首次访问最深叶子仍可能走Θ(log n)条边。后续访问变快不否定这个反例。数组下标与秩按固定字长RAM计单位成本；Python教学实现不用于验证任意位长运算的常数代价。

与独立划分参照核对

运行 python3 examples/advanced-algorithms/check_dsu.py。本次n=4、长度0–3的4369条合并序列共12816步通过，另有n=32、seed20260919的2000步随机合并及31项异常检查。深度3路径完整压缩且rank不变的用例也通过。原始结果在 examples/advanced-algorithms/results/dsu.json，配套检查卡记录范围。参照为每个顶点保存分量标签，合并时扫描全部顶点，把一组旧标签改成另一组。这个参照很慢，却不使用森林或路径压缩，能检出与优化实现不同类别的错误。每次合并后比较所有顶点对的连通性，比只核对find返回的具体根编号更合适，因为两个正确实现可以选择不同代表元。

失效边界可以用三个顶点直接检验：加入边(0,1)和(1,2)后，三者在同一集合；若删除(1,2)，原图中2已孤立，旧并查集却仍回答0与2连通。问题不在于find压缩得不够，而是状态没有保存足以处理拆分的信息。离线删边、回滚或动态森林需要额外方法，留到选修E01。

练习

  1. 对8个单点集合只合并同秩根，构造秩3的根。画出首次find前后的一条最长路径，列出哪些parent改变、哪些rank保持不变。
  2. 扩展朴素标签参照以输出每个分量的完整成员集合，与并查集逐项比较。为什么不应断言两者代表元编号相等？再给出删边后两者需要重新计算的例子。

参考资料