最小生成树——Kruskal 算法

按学院培养方案，大一下学期你们要学离散数学，图论是其中一部分。李梦巧老师很严格，小心挂科！

问题回顾

给定一个 $n$ 个节点 $m$ 条边的无向带权连通图，求最小生成树的边权和。

生成树：选出 $n-1$ 条边，使 $n$ 个节点全部连通且无环。

最小生成树 (MST)：在所有生成树中，边权和最小的那棵。

Kruskal 算法

贪心策略：每次选当前权值最小的边，若加入后不会形成环，就加入 MST。

为什么贪心是对的？—— MST 的割性质：对于图中任意一个割（将图分成两部分），连接这两部分的最小权边一定属于某个 MST。Kruskal 本质上就是在不断寻找切割的最小权边。

算法流程

1. 将所有边按权值从小到大排序
2. 初始化并查集，每个节点自成一派
3. 遍历排序后的边：
   • 若边的两端已连通（find 相同）→ 加入会成环，跳过
   • 否则 → 合并两端（unite），累加权值
4. 选够 $n-1$ 条边即结束

与上一题的呼应

上一题"demon的荒岛求生"学了并查集，本题恰好用上：排序 + 并查集判环 = Kruskal。数据结构就是这样一环扣一环。

复杂度

• 排序：$O(m \log m)$
• 每条边做一次并查集操作：$O(m \cdot \alpha(n)) \approx O(m)$

总体 $O(m \log m)$。

完整代码

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

const int MAXN = 1005;
int parent[MAXN];

struct Edge {
    int a, b, w;
    bool operator<(const Edge& o) const { return w < o.w; }
};

int find(int x) {
    while (parent[x] != x) {
        parent[x] = parent[parent[x]];
        x = parent[x];
    }
    return x;
}

bool unite(int a, int b) {
    a = find(a); b = find(b);
    if (a != b) { parent[a] = b; return true; }
    return false;
}

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

    int n, m;
    cin >> n >> m;
    vector<Edge> edges(m);
    for (int i = 0; i < m; i++)
        cin >> edges[i].a >> edges[i].b >> edges[i].w;
    sort(edges.begin(), edges.end());

    for (int i = 1; i <= n; i++) parent[i] = i;

    int ans = 0, cnt = 0;
    for (int i = 0; i < m && cnt < n - 1; i++) {
        if (unite(edges[i].a, edges[i].b)) {
            ans += edges[i].w;
            cnt++;
        }
    }
    cout << ans << '\n';
    return 0;
}