设备网络不断加边时反复 DFS 判断两点是否连通会浪费历史结果。本文用并查集解释路径压缩与按秩合并如何维护连通块并给出 Java 运行测试。文中同步标出复杂度、边界条件和可复制测试方便把思路带进真实项目验证。把楼层交换机画成图后运营同学每新增一根线就问两台设备能不能互通。每次都从头 DFS 当然正确但前一天已经确认过的连通块被白白重算。并查集不保存完整路径只为每个集合保存一个代表元新增边时合并代表元查询时比较代表元正适合“只加边、频繁问连通性”的账本。先把问题的边界画出来这类题最容易被“有一个现成名词”带偏。先不急着选数据结构先写清输入在何时到达、输出需要何时可用、更新是否允许撤销以及结果是精确值还是候选值。这个四问能排除很多表面可运行、线上却无法解释的方案。示例把状态、停止条件和异常分开写目的不是增加篇幅而是让测试能对应到每一条承诺。find 沿 parent 指针找到根。路径压缩在返回时把沿途节点直接指向根下次查询更短union 先找两根再让较矮的树挂到较高树避免形成长链。两项优化一起使用后均摊复杂度接近常数严格说是 O(alpha(n))。把不变量变成代码动作可以按一次合并来观察初始 0、1、2 各自为根合并 0-1 后根数减少一再合并 1-2 时find(1) 先到 02 挂到 0。重复合并同一集合不应改变 size。示例暴露 count方便验证网络分区数是否随合法合并准确减少。实现时建议先在纸上走一遍最短样例空输入、一个元素、刚好跨越临界值和重复值。每执行一行就问一次“此前成立的约束是否仍成立”。这种手工模拟尤其能发现索引偏移、先后顺序和状态未重置的问题。等不变量清楚后优化才不会改变语义。放进工程链路时的分寸工程实现应先定义输入版本、权限边界和错误返回再考虑把核心计算放到哪个进程。对需要持续运行的任务记录请求规模、算法版本和拒绝原因比只保留成功标记更便于复盘任何外部依赖都应被替换为可控的本地测试桩。另一个常被忽略的点是可观测性。记录输入规模、耗时、拒绝原因和算法版本比只记录一个成功标记更有用。数据异常时先确认是否违反了算法前提再怀疑实现很多“性能回归”其实只是分布变了。把这些字段作为接口契约的一部分线上复盘才不需要猜测。可直接运行的实现publicclassUnionFindDemo{staticclassDSU{int[]p,rank;intcount;DSU(intn){pnewint[n];ranknewint[n];countn;for(inti0;in;i)p[i]i;}intfind(intx){if(x0||xp.length)thrownewIllegalArgumentException();returnp[x]x?x:(p[x]find(p[x]));}booleanunion(inta,intb){intxfind(a),yfind(b);if(xy)returnfalse;if(rank[x]rank[y]){inttx;xy;yt;}p[y]x;if(rank[x]rank[y])rank[x];count--;returntrue;}booleanconnected(inta,intb){returnfind(a)find(b);}}publicstaticvoidmain(String[]args){DSUdnewDSU(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。这些断言刻意包含正例和负例。正例证明主要路径能走通负例证明代码没有靠偶然输入蒙对。把它们放进持续集成时应使用固定输入和确定输出涉及随机、时间或网络的逻辑要注入可控依赖避免测试本身成为不稳定来源。复核 连通性查询别重建图并查集的合并账本 时把输入规模从小到大递增并保留每一轮的状态快照。若结果变化无法由前述不变量解释就应先缩小复现用例而不是立刻添加特殊分支。对 并查集 而言正确性与可部署性要同时检查前者由断言和反例支撑后者由资源上限、错误返回和版本记录支撑。把两者混为一谈往往会让一次优化埋下新的边界缺陷。阅读代码时可尝试替换一个关键输入例如把端点换成相等、把规模换成零、把顺序打乱。若行为仍能用本文的状态定义说明说明实现没有偷偷依赖样例中的偶然规律。复核 连通性查询别重建图并查集的合并账本 时把输入规模从小到大递增并保留每一轮的状态快照。若结果变化无法由前述不变量解释就应先缩小复现用例而不是立刻添加特殊分支。对 并查集 而言正确性与可部署性要同时检查前者由断言和反例支撑后者由资源上限、错误返回和版本记录支撑。把两者混为一谈往往会让一次优化埋下新的边界缺陷。阅读代码时可尝试替换一个关键输入例如把端点换成相等、把规模换成零、把顺序打乱。若行为仍能用本文的状态定义说明说明实现没有偷偷依赖样例中的偶然规律。复核 连通性查询别重建图并查集的合并账本 时把输入规模从小到大递增并保留每一轮的状态快照。若结果变化无法由前述不变量解释就应先缩小复现用例而不是立刻添加特殊分支。对 并查集 而言正确性与可部署性要同时检查前者由断言和反例支撑后者由资源上限、错误返回和版本记录支撑。把两者混为一谈往往会让一次优化埋下新的边界缺陷。阅读代码时可尝试替换一个关键输入例如把端点换成相等、把规模换成零、把顺序打乱。若行为仍能用本文的状态定义说明说明实现没有偷偷依赖样例中的偶然规律。复核 连通性查询别重建图并查集的合并账本 时把输入规模从小到大递增并保留每一轮的状态快照。若结果变化无法由前述不变量解释就应先缩小复现用例而不是立刻添加特殊分支。对 并查集 而言正确性与可部署性要同时检查前者由断言和反例支撑后者由资源上限、错误返回和版本记录支撑。把两者混为一谈往往会让一次优化埋下新的边界缺陷。收束并查集的聪明之处在于它只维护问题需要的事实。若需求是增量连通性保存每条搜索路径反而是多余负担。真正可维护的算法代码不靠注释堆砌而靠名称、不变量和测试彼此印证。下一次需求变化时先检查它是否破坏本文列出的前提再决定扩展实现还是更换模型。
