#4408. [GESP202512 八级 C++] 第 15 题

[GESP202512 八级 C++] 第 15 题

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

{{ select(1) }}

  • 必须选入 MST,否则可能不连通。
  • 一定不能选入 MST(在此扫描顺序下)。
  • 若后续出现更大的边权,可以回溯改选 ee
  • 只有当 ee 是当前最小边时才能舍弃。