c++Kruskal 最小生成树

#include <bits/stdc++.h>
using namespace std;

// 边结构体：存储两个端点 + 边权
struct Edge {
    int u, v;
    int w;
};

// 并查集数组（父节点）
int fa[200005];

// 查找根节点（带路径压缩）
int findfa(int x){
    if(fa[x] == x)        // 若 x 即是根
        return x;
    return fa[x] = findfa(fa[x]);  // 路径压缩
}

// 合并两个集合（成功合并返回 true）
bool unite(int a, int b){
    a = findfa(a);
    b = findfa(b);
    if(a != b){
        fa[b] = a;
        return true;
    }
    return false;
}

// 传统 C++98 比较函数
bool cmp(const Edge &a, const Edge &b){
    return a.w < b.w;  // 按边权升序
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    int n, m;
    cin >> n >> m;  // n 点 m 边

    vector<Edge> edges(m);

    // 输入所有边
    for(int i=0; i<m; i++){
        cin >> edges[i].u >> edges[i].v >> edges[i].w;
    }

    // 初始化并查集（自己是自己的父亲）
    for(int i=1; i<=n; i++){
        fa[i] = i;
    }

    // 按权值排序（从小到大）
    sort(edges.begin(), edges.end(), cmp);

    long long mst = 0;   // 最小生成树权值和
    int cnt = 0;         // 已选的边数量

    // 枚举边，依次尝试加入 MST
    for(int i=0; i<m; i++){
        // 若边的两个端点在不同集合，则选取
        if(unite(edges[i].u, edges[i].v)){
            mst += edges[i].w;  // 累加权值
            cnt++;
            if(cnt == n - 1)    // 已选到 n-1 条边，完成
                break;
        }
    }

    // 输出最小生成树权值和
    cout << mst << "\n";

    return 0;
}

✅ 输入样例

4 5
1 2 1
1 3 4
2 3 2
2 4 7
3 4 3

✅ 输出样例

6

✅ 说明

最小生成树由边：

• 1–2：1

• 2–3：2

• 3–4：3
  合计：1 + 2 + 3 = 6