c++kruskal算法求最小生成树

Kruskal算法是一种基于贪心思想的最小生成树算法，其基本思路是将所有边按照权值从小到大排序，然后依次加入到最小生成树中，如果加入后形成了环，则不加入该边。

具体实现步骤如下：

1. 将所有边按照权值从小到大排序。

2. 初始化一个并查集，每个节点都是一个单独的集合。

3. 依次取出排序后的边，如果该边的两个端点不在同一个集合中，则将其加入最小生成树中，并将这两个端点所在的集合合并。

4. 最后得到的最小生成树就是答案。

下面是C++代码实现：

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

const int N = 100010;

int n, m;
int p[N];

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

vector<Edge> edges;

int find(int x) {
    if (p[x] != x) p[x] = find(p[x]);
    return p[x];
}

int kruskal() {
    sort(edges.begin(), edges.end());
    for (int i = 1; i <= n; i++) p[i] = i;
    int res = 0, cnt = 0;
    for (auto& e : edges) {
        int fa = find(e.a), fb = find(e.b);
        if (fa != fb) {
            p[fa] = fb;
            res += e.w;
            cnt++;
            if (cnt == n - 1) break;
        }
    }
    if (cnt < n - 1) return -1; // 无法构成生成树
    return res;
}

int main() {
    cin >> n >> m;
    while (m--) {
        int a, b, w;
        cin >> a >> b >> w;
        edges.push_back({a, b, w});
    }
    int res = kruskal();
    if (res == -1) cout << "impossible" << endl;
    else cout << res << endl;
    return 0;
}

时间复杂度为O(mlogm)，其中m为边数，因为需要对所有边进行排序。