跳到主要内容

AcWing 859. Kruskal 算法求最小生成树

本节目标

按边权从小到大尝试选边，仅连接不同连通块来构造最小生成树。

这是最小生成树的边排序母题。需要的连通块查询与合并约定见8.3 连通性、并查集与二分图。

查看 AcWing 原题

题意与约束​

给定无向带权图，输出最小生成树总权值；如果图不连通，输出 impossible。每条边至多被考虑一次，重边可以同时保留，排序后自然优先尝试较轻者。

直接思路与瓶颈​

可以枚举所有恰好含 n-1 条边的子集，再检查连通、无环和总权值，但候选数量是组合级的，无法处理较多边。也不能只取全图最轻的 n-1 条边：它们可能形成环而遗漏其他连通块。需要在每次选边时同时知道两端是否已被当前森林连通。

图模型与算法推导​

将无向图保留为边表，按权值从小到大排序；并查集维护当前已选边形成的连通块（find、路径压缩和按大小合并见8.3 连通性、并查集与二分图）。扫描每条边：两端属于不同集合就选入、合并并累加，否则跳过。已选边始终是一片森林，直到选满 n-1 条边。

正确性依据​

设当前已选边构成森林。对一条两端属于不同连通块的待选边，取其中一个连通块为一侧、其余顶点为另一侧；它跨越这个切分。所有更轻的边已经先被扫描：若它跨越同一切分且可接纳，就会在更早时合并这两个部分；若不可接纳，则已在某个块内，不能替代当前连接。因此当前最轻的可接纳跨切分边满足切分性质，可安全加入某棵最小生成树。块内边会形成环，不选不会降低任何连通需要。反复加入安全边，选满 n-1 条时得到连通且无环的最小生成树；若不足，则原图不连通。

样例执行过程​

输入：

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

按边权排序为 (1,2,1)、(2,3,2)、(1,3,3)、(2,4,4)、(3,4,5)；初始连通块为 {1},{2},{3},{4}，总权值为 0。

  1. 选 (1,2,1)：合并为 {1,2},{3},{4}，总权值为 1。
  2. 选 (2,3,2)：合并为 {1,2,3},{4}，总权值为 3。
  3. 检查 (1,3,3)：两端已在 {1,2,3}，会成环，跳过。
  4. 选 (2,4,4)：得到 {1,2,3,4}，总权值为 7，已选 3 条边即 n-1 条，最终答案为 7。

代码实现​

排序后，只有 unite 成功时才累计边权并增加边数。最终边数必须等于 n - 1；否则结果只是最小生成森林，不能作为题目的生成树答案。

C++17
#include <algorithm>
#include <climits>
#include <iostream>
#include <numeric>
#include <vector>
using namespace std;

struct Edge {
    int from;
    int to;
    long long weight;

    bool operator<(const Edge& other) const {
        return weight < other.weight;
    }
};

class DisjointSet {
public:
    explicit DisjointSet(int n) : parent(n + 1), size(n + 1, 1) {
        iota(parent.begin(), parent.end(), 0);
    }

    bool unite(int first, int second) {
        first = find(first);
        second = find(second);
        if (first == second) return false;
        if (size[first] < size[second]) swap(first, second);
        parent[second] = first;
        size[first] += size[second];
        return true;
    }

private:
    vector<int> parent;
    vector<int> size;

    int find(int vertex) {
        if (parent[vertex] != vertex) parent[vertex] = find(parent[vertex]);
        return parent[vertex];
    }
};

long long kruskal(int n, vector<Edge>& edges) {
    sort(edges.begin(), edges.end());

    DisjointSet sets(n);
    long long totalWeight = 0;
    int edgeCount = 0;
    for (const auto& edge : edges) {
        if (sets.unite(edge.from, edge.to)) {
            totalWeight += edge.weight;
            edgeCount++;
        }
    }
    return edgeCount == n - 1 ? totalWeight : LLONG_MAX;
}

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

    int n, m;
    cin >> n >> m;
    vector<Edge> edges(m);
    for (auto& edge : edges) cin >> edge.from >> edge.to >> edge.weight;

    const long long answer = kruskal(n, edges);
    if (answer == LLONG_MAX) {
        cout << "impossible\n";
    } else {
        cout << answer << '\n';
    }
    return 0;
}

复杂度分析​

排序 m 条边需要 O(m log m)，其余连通块操作近似线性；边表、并查集使用 O(n + m) 空间。

边界与易错点​

  • 只在合并成功时加权值与边数。
  • 自环和块内边必须跳过。
  • 不能省略 edgeCount == n - 1 的连通性检查。
  • 图是无向图，但边表每条边只需处理一次。

模式迁移​

凡是“选最轻可接纳边、避免环、最终连通”的显式边表题都可从 Kruskal 开始；复杂连通块操作仍回到 8.3 的约定。