如何通过两次DFS遍历在O(V+E)时间求解边权为x/y的无向图MST？

咱来给你把这个思路拆解透——这个方法的核心就是利用边权只有两种的特性，跳过传统Kruskal/Prim里的排序开销，用两次DFS就能搞定，完全符合O(V+E)的时间要求。

先明确核心逻辑：因为x<y，要做最小生成树，肯定要尽可能多用低权的x边，只有当x边没法连通两个分量时，才不得不使用y边。基于这个逻辑，整个流程分成三步：

第一步：用DFS划分「超级节点」 #

我们只关注权值为x的边，把所有通过x边连通的节点合并成一个“超级节点”——说白了就是找x边构成的所有连通分量：

• 初始化所有节点为未访问状态
• 遍历每个未访问的节点，启动DFS，沿着所有x边遍历所有可达节点，给这些节点打上同一个超级节点ID
  这一步的时间是O(V+E)，因为每个节点和x边只会被处理一次，完全线性。

第二步：构建超级节点的缩图 #

把每个超级节点当成缩图里的一个新节点，然后处理原图形中的y边：

• 遍历所有y边，如果这条边连接的两个节点属于不同的超级节点，就在缩图里加一条连接这两个超级节点的边（注意去重，同一对超级节点之间的多条y边只需要保留一条就行）
  缩图的规模远小于原图，这一步也是线性时间，因为只遍历所有y边。

第三步：第二次DFS计算MST总权值 #

因为原图是连通的，缩图肯定也是连通的。我们只需要知道超级节点的数量S，就能直接算出MST的总权值：

• x边的总贡献：(V - S) * x —— 每个超级节点内部是用x边连通的，每个大小为k的超级节点需要k-1条x边，所有超级节点加起来就是总节点数V减去超级节点数S
• y边的总贡献：(S - 1) * y —— 要把S个独立的超级节点连通成一个整体，最少需要S-1条y边（这就是缩图的生成树边数）
• 把两者相加就是MST的最小总权值

举两个极端例子验证下：

• 如果所有边都是x边：S=1，总权值就是(V-1)*x，完全符合生成树的要求
• 如果没有x边：S=V，总权值就是(V-1)*y，也是正确的生成树结果

整个流程下来，两次DFS加一次边遍历，都是O(V+E)的时间，完美满足要求。

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