GESP 八级 · GESP 202512 C++ 八级 第 15 题

对连通无向图执行 Kruskal 算法。已按边权从小到大依次扫描到某条边 $e = (u, v)$。此时在已经构建的部分 MST 结构中，$(u, v)$ 已在同一连通块内。关于边 $e$ 的处理，下列说法正确的是（ ）。

回溯法在搜索过程中不断剪枝，当发现当前选择不可能得到解时立即返回。关键在于合理设计剪枝条件。

回溯后必须撤销选择（恢复现场），否则影响后续分支的搜索。先判断剪枝条件再递归可以大幅优化效率。

【考点】Kruskal 算法｜并查集连通性判断｜MST 贪心性质

🎯 考纲定位 GESP 八级图论核心考点。命题人专卡“已连通边必舍弃”这一细节——学生常误以为边权小就要保留，却忽略连通块判定才是 MST 构建的唯一依据。此题即检验对算法流程的机械执行与本质理解的差距。

🧠 解题思维 Kruskal 按边权升序遍历，遇到 $(u, v)$ 先查并查集：若 find(u) == find(v)，说明 $u, v$ 已在同一连通块，加入必成环；因算法已按从小到大扫描，后续更小的边不可能再连接这两点，故直接跳过。反之才合并。此通法适用于所有基于边排序的 MST 算法，核心是“连通性优先于边权大小”。

🪤 陷阱拆解 A 错在“可能不连通”：原图连通，$u, v$ 已连，加 $e$ 不会改善连通性，只会冗余。C 错在“回溯改选”：Kruskal 是贪心单向扫描，一旦判定丢弃永不回看，不存在“后续更大边权”可补救。D 错在“当前最小”：舍弃条件与边权大小无关，只取决于连通性；即使 $e$ 是当前最小，只要 $u, v$ 已连通就必须舍弃。命题人用绝对化表述（“必须”“一定不能”“只有当”）诱导学生混淆“必要条件”与“充分条件”。

🔄 反命题思维 若将题干改为"$u, v$ 不在同一连通块”，答案则翻转为“必须选入”。若换为 Prim 算法，判断逻辑从“并查集同根”变为“顶点是否已在树中”，但贪心本质不变。刷到此类题先问：命题人想让我验证哪条规则？是连通性还是边权顺序？