连通性查询别重建图：并查集的合并账本

设备网络不断加边时，反复 DFS 判断两点是否连通会浪费历史结果。本文用并查集解释路径压缩与按秩合并如何维护连通块，并给出 Java 运行测试。文中同步标出复杂度、边界条件和可复制测试，方便把思路带进真实项目验证。

把楼层交换机画成图后，运营同学每新增一根线就问两台设备能不能互通。每次都从头 DFS 当然正确，但前一天已经确认过的连通块被白白重算。并查集不保存完整路径，只为每个集合保存一个代表元；新增边时合并代表元，查询时比较代表元，正适合“只加边、频繁问连通性”的账本。

先把问题的边界画出来

这类题最容易被“有一个现成名词”带偏。先不急着选数据结构，先写清输入在何时到达、输出需要何时可用、更新是否允许撤销，以及结果是精确值还是候选值。这个四问能排除很多表面可运行、线上却无法解释的方案。示例把状态、停止条件和异常分开写，目的不是增加篇幅，而是让测试能对应到每一条承诺。

find 沿 parent 指针找到根。路径压缩在返回时把沿途节点直接指向根，下次查询更短；union 先找两根，再让较矮的树挂到较高树，避免形成长链。两项优化一起使用后，均摊复杂度接近常数，严格说是 O(alpha(n))。

把不变量变成代码动作

可以按一次合并来观察：初始 0、1、2 各自为根；合并 0-1 后根数减少一；再合并 1-2 时，find(1) 先到 0，2 挂到 0。重复合并同一集合不应改变 size。示例暴露 count，方便验证网络分区数是否随合法合并准确减少。

实现时建议先在纸上走一遍最短样例：空输入、一个元素、刚好跨越临界值和重复值。每执行一行，就问一次“此前成立的约束是否仍成立”。这种手工模拟尤其能发现索引偏移、先后顺序和状态未重置的问题。等不变量清楚后，优化才不会改变语义。

放进工程链路时的分寸

工程实现应先定义输入版本、权限边界和错误返回，再考虑把核心计算放到哪个进程。对需要持续运行的任务，记录请求规模、算法版本和拒绝原因，比只保留成功标记更便于复盘；任何外部依赖都应被替换为可控的本地测试桩。

另一个常被忽略的点是可观测性。记录输入规模、耗时、拒绝原因和算法版本，比只记录一个成功标记更有用。数据异常时，先确认是否违反了算法前提，再怀疑实现；很多“性能回归”其实只是分布变了。把这些字段作为接口契约的一部分，线上复盘才不需要猜测。

可直接运行的实现

publicclassUnionFindDemo{staticclassDSU{int[]p,rank;intcount;DSU(intn){p=newint[n];rank=newint[n];count=n;for(inti=0;i<n;i++)p[i]=i;}intfind(intx){if(x<0||x>=p.length)thrownewIllegalArgumentException();returnp[x]==x?x:(p[x]=find(p[x]));}booleanunion(inta,intb){intx=find(a),y=find(b);if(x==y)returnfalse;if(rank[x]<rank[y]){intt=x;x=y;y=t;}p[y]=x;if(rank[x]==rank[y])rank[x]++;count--;returntrue;}booleanconnected(inta,intb){returnfind(a)==find(b);}}publicstaticvoidmain(String[]args){DSUd=newDSU(4);d.union(0,1);d.union(1,2);if(!d.connected(0,2)||d.connected(0,3)||d.count!=2)thrownewAssertionError();System.out.println(d.connected(0,2));}}

复杂度不是一句口号

m 次 union/find 的总成本为 O(m alpha(n))，实际几乎线性；parent 和 rank 数组占 O(n) 空间。没有路径压缩时，最坏链会让单次 find 到 O(n)。

分析复杂度时要说明 n 到底代表什么：请求数、节点数、字符数还是窗口长度。只写一个 O(n) 往往掩盖了排序、哈希冲突、输出大小或网络等待等隐含成本。本文的程序将算法核心与输入输出分离，测试输出只用于验证，不应被当作真实性能数据。

边界条件和常见误区

**边界条件。**元素数为零时不能查询；同一节点 union 自身应返回 false；编号越界要抛异常；若业务支持删除边，需要离线回滚并查集或动态连通性算法，不能硬删 parent。

**常见错误。**把 parent[x]=y 当作合并而不先找根会制造错误层级；只做按秩不做压缩仍可能有额外成本；用 size 判断连通而不是根相等没有逻辑保证。

上线前还应把错误策略定下来：是抛异常、返回空结果、降级到慢路径，还是排队等待。不同选择都有成本，关键是不能让调用方从一个看似正常的返回值里猜测失败。对涉及用户数据的场景，日志同样应遵守最小化记录原则。

复制即可执行的测试

程序合并 0-1 和 1-2，断言 0 与 2 连通、0 与 3 不连通，集合数从四变为二；最后打印 true。

这些断言刻意包含正例和负例。正例证明主要路径能走通，负例证明代码没有靠偶然输入蒙对。把它们放进持续集成时，应使用固定输入和确定输出；涉及随机、时间或网络的逻辑要注入可控依赖，避免测试本身成为不稳定来源。

复核 连通性查询别重建图：并查集的合并账本 时，把输入规模从小到大递增，并保留每一轮的状态快照。若结果变化无法由前述不变量解释，就应先缩小复现用例，而不是立刻添加特殊分支。

对 并查集 而言，正确性与可部署性要同时检查：前者由断言和反例支撑，后者由资源上限、错误返回和版本记录支撑。把两者混为一谈，往往会让一次优化埋下新的边界缺陷。

阅读代码时可尝试替换一个关键输入，例如把端点换成相等、把规模换成零、把顺序打乱。若行为仍能用本文的状态定义说明，说明实现没有偷偷依赖样例中的偶然规律。

复核 连通性查询别重建图：并查集的合并账本 时，把输入规模从小到大递增，并保留每一轮的状态快照。若结果变化无法由前述不变量解释，就应先缩小复现用例，而不是立刻添加特殊分支。

对 并查集 而言，正确性与可部署性要同时检查：前者由断言和反例支撑，后者由资源上限、错误返回和版本记录支撑。把两者混为一谈，往往会让一次优化埋下新的边界缺陷。

阅读代码时可尝试替换一个关键输入，例如把端点换成相等、把规模换成零、把顺序打乱。若行为仍能用本文的状态定义说明，说明实现没有偷偷依赖样例中的偶然规律。

复核 连通性查询别重建图：并查集的合并账本 时，把输入规模从小到大递增，并保留每一轮的状态快照。若结果变化无法由前述不变量解释，就应先缩小复现用例，而不是立刻添加特殊分支。

对 并查集 而言，正确性与可部署性要同时检查：前者由断言和反例支撑，后者由资源上限、错误返回和版本记录支撑。把两者混为一谈，往往会让一次优化埋下新的边界缺陷。

阅读代码时可尝试替换一个关键输入，例如把端点换成相等、把规模换成零、把顺序打乱。若行为仍能用本文的状态定义说明，说明实现没有偷偷依赖样例中的偶然规律。

复核 连通性查询别重建图：并查集的合并账本 时，把输入规模从小到大递增，并保留每一轮的状态快照。若结果变化无法由前述不变量解释，就应先缩小复现用例，而不是立刻添加特殊分支。

对 并查集 而言，正确性与可部署性要同时检查：前者由断言和反例支撑，后者由资源上限、错误返回和版本记录支撑。把两者混为一谈，往往会让一次优化埋下新的边界缺陷。

收束

并查集的聪明之处在于它只维护问题需要的事实。若需求是增量连通性，保存每条搜索路径反而是多余负担。

真正可维护的算法代码不靠注释堆砌，而靠名称、不变量和测试彼此印证。下一次需求变化时，先检查它是否破坏本文列出的前提，再决定扩展实现还是更换模型。