最小生成树 · Kruskal

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

const int N = 100010;

// ========== 并查集部分 ==========
int parent[N];  // parent[i] 表示节点 i 的父节点

// 查找节点 x 所属集合的代表元素（带路径压缩）
int find(int x) {
    if (parent[x] != x)              // 如果 x 不是自己的父节点
        parent[x] = find(parent[x]); // 递归找根，并压缩路径
    return parent[x];                // 返回根节点
}

// 合并两个集合：把 x 和 y 所在的集合连起来
void merge(int x, int y) {
    int rx = find(x);  // 找到 x 的根
    int ry = find(y);  // 找到 y 的根
    if (rx != ry)      // 如果根不同（不在同一集合）
        parent[rx] = ry; // 把 x 的根指向 y 的根
}

// ========== 边的结构体 ==========
struct Edge {
    int u, v, w;  // u-v 之间有一条权重为 w 的边
};

// 自定义排序：按边权从小到大排序
bool cmp(Edge a, Edge b) {
    return a.w < b.w;  // w 小的排前面
}

// ========== Kruskal 主算法 ==========
int kruskal(vector<Edge>& edges, int n) {
    // 第1步：把所有边按权重从小到大排序
    sort(edges.begin(), edges.end(), cmp);

    // 第2步：初始化并查集——每个节点最初是自己的父节点
    for (int i = 0; i < n; i++)
        parent[i] = i;

    int mstWeight = 0;  // 最小生成树的总权值
    int edgeCount = 0;  // 已经选了多少条边

    // 第3步：依次考虑每条边
    for (auto& e : edges) {
        // 检查：这条边的两个端点是否在同一集合？
        if (find(e.u) != find(e.v)) {
            // 不在同一集合 → 加入这条边不会形成环
            merge(e.u, e.v);      // 合并两个集合
            mstWeight += e.w;      // 累加边权
            edgeCount++;           // 选中的边数+1
            if (edgeCount == n - 1)
                break;  // 已经选了 n-1 条边，MST 完成
        }
        // 如果在同一集合 → 加入会形成环，跳过
    }
    return mstWeight;
}

int main() {
    int n, m;  // n个顶点，m条边
    cin >> n >> m;
    vector<Edge> edges(m);
    for (int i = 0; i < m; i++)
        cin >> edges[i].u >> edges[i].v >> edges[i].w;

    cout << kruskal(edges, n) << endl;
    return 0;
}