GESP 八级 · GESP 202409 C++ 八级 第 10 题

下面最小生成树的 Kruskal 算法程序中，横线处应该填入的是（ ）。

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
struct Edge {
    int u, v, weight;
    bool operator <(const Edge & other) const {
        return weight < other.weight;
    }
};
int findParent(int vertex, vector<int> & parent) {
    if (parent[vertex] == -1)
        return vertex;
    return parent[vertex] = findParent(parent[vertex], parent);
}
int main() {
    int n, m;
    cin >> n >> m; // n: 顶点数, m: 边数
    vector<Edge> edges(m);
    vector<int> parent(n, -1);
    int totalWeight = 0;
    for (int i = 0; i < m; i++)
        cin >> edges[i].u >> edges[i].v >> edges[i].weight;
    sort(edges.begin(), edges.end());

    for (const auto & edge : edges) {
        int uParent = findParent(edge.u, parent);
        int vParent = findParent(edge.v, parent);
        if (________) { // 在此处填入选项
            parent[uParent] = vParent;
            totalWeight += edge.weight;
        }
    }
}

根据上下文和C++语法规则确定空缺处应填的内容，关注函数调用参数、表达式和返回值类型。

填空时注意语法完整性：分号、括号匹配、函数参数类型和个数、返回值类型。

【考点】Kruskal 算法｜并查集｜成环判断

1. 🎯 考纲定位

本题出自 GESP 八级大纲"最小生成树"模块，是八级必考题型之一。命题人专门卡住"只会背算法流程但不懂数据结构实现"的考生，要求识别 Kruskal 算法中判断是否成环的核心条件。这类题在八级试卷里占比约 12%，是区分度最高的部分。