异星工厂：简单火车——按分量选择最轻出边¶

Codex（GPT-6）将经典 Borůvka 算法应用于非正边收缩后的图，程序为 alternative.cpp。非正边处理沿用出题人方法，详见主解。

每轮合并¶

加入全部非正边后，重复以下操作：

扫描全部正边，为每个当前分量记录最轻的出边。
依次处理这些候选边；若端点尚未连通，就选择该边、加上费用并合并。
若整轮没有合并，停止；否则继续，直到只剩一个分量。

同一条边可能被两端分量同时选中，必须在加入时再次检查并查集，不能重复计费。费用相同时保持较早的输入边：扫描顺序固定，并且只有严格更轻时才替换候选。

正确性¶

每个候选都是一个当前分量割上的最轻边，因此满足最小生成树的割性质。用边的输入序号作为第二排序键，可将相同费用的边排成一致的严格次序；每个割的候选边都是该次序下的唯一最小边。这些边属于同一棵按该次序确定的最小生成树，可以一起安全加入。重复候选或已连通候选由并查集跳过。

反复合并得到最小生成树；若停下时仍有多个分量，由于扫描过全部边且找不到可合并候选，原图无法连通。连同必须加入的负边及可免费加入的零边，总费用最优。

复杂度与取舍¶

在任一尚未完成的连通区域内，每个分量都选择至少一条出边，一轮后每个合并结果至少包含两个旧分量，所以分量数量至少减半。孤立分量不再变化；所有区域至多经历 \(O(\log(n+1))\) 个有效阶段，再加一次停止检查。

当前实现每轮初始化和遍历长度为 \(n+1\) 的候选表，并扫描所有边。时间界为 \(O((n+m\alpha(n))\log(n+1))\) ，空间为 \(O(n+m)\) .它避免全局排序，但会多次扫描边，并额外使用一个候选数组。与 Kruskal 相比没有统一的实际速度优势，作为不同合并策略的备用方案保留；见实测。