默认边权为3的完全图给定部分权1边时如何高效求解MST

• 核心逻辑基于Kruskal算法优先选择最小权重边的规则，由于场景中仅存在权重1和3两种边，不需要构建完整完全图，仅处理给定的M条权重为1的边即可。
• 使用并查集（DSU）数据结构维护节点连通关系，处理完所有M条权重为1的边后，统计当前的连通分量总数cnt。

总权重计算公式 #

总权重 = (N - cnt) * 1 + (cnt - 1) * 3 = N + 2 * cnt - 3

公式解释：

• 每个连通分量内部已通过权重为1的边连接，所有分量的内部边总数量为N - cnt，对应权重贡献为N - cnt
• 要将cnt个连通分量合并为一棵生成树，需要cnt - 1条跨分量边，这类边的默认权重为3，对应权重贡献为3 * (cnt - 1)

复杂度说明 #

• 时间复杂度为O(M*α(N))，其中α是阿克曼函数的反函数，取值基本不超过5，可轻松处理M到1e5量级的输入
• 空间复杂度为O(N + M)，仅需要存储并查集数组和M条权重为1的边，无需存储完全图的其余边

示例验证 #

示例输入：

5 4
1 5
1 4
4 2
4 3

处理完4条权重为1的边后，所有5个节点属于同一个连通分量，即cnt = 1，代入公式得总权重为5 + 2 * 1 - 3 = 4，和示例MST的总权重完全匹配。

内容的提问来源于stack exchange，提问作者JameEnder