克鲁斯卡尔算法，c++

克鲁斯卡尔算法（Kruskal算法）是一种用于求解最小生成树的贪心算法。以下是C++实现：

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

const int MAXN = 1005;  // 定义最大点数
int father[MAXN];  // 定义并查集数组

struct Edge {
    int u, v, w;
    Edge(int u, int v, int w): u(u), v(v), w(w) {}
};

bool cmp(const Edge &a, const Edge &b) {
    return a.w < b.w;
}

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

void merge(int x, int y) {
    int fx = find(x);
    int fy = find(y);
    if (fx != fy) {
        father[fx] = fy;
    }
}

int kruskal(int n, vector<Edge> edges) {
    for (int i = 1; i <= n; i++) {
        father[i] = i;
    }
    sort(edges.begin(), edges.end(), cmp);
    int ans = 0;
    for (int i = 0; i < edges.size(); i++) {
        int u = edges[i].u;
        int v = edges[i].v;
        int w = edges[i].w;
        if (find(u) != find(v)) {
            merge(u, v);
            ans += w;
        }
    }
    return ans;
}

int main() {
    int n, m;
    cin >> n >> m;
    vector<Edge> edges;
    for (int i = 0; i < m; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        edges.push_back(Edge(u, v, w));
    }
    int ans = kruskal(n, edges);
    cout << ans << endl;
    return 0;
}

其中，`find`函数实现了路径压缩，`merge`函数实现了按秩合并，`kruskal`函数实现了克鲁斯卡尔算法。时间复杂度为$O(m\log m)$，其中$m$为边数。