用c++写一个程序实现采用克鲁斯卡尔算法求最小生成树

好的，以下是用C++实现克鲁斯卡尔算法求最小生成树的程序：

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

const int MAX_N = 1000; // 最大节点数
const int MAX_M = 100000; // 最大边数

struct Edge {
    int u, v, w; // 边的信息：起点、终点、权值
} edges[MAX_M];

int n, m; // 节点数、边数
int fa[MAX_N]; // 并查集数组

// 并查集的查找操作
int find(int x) {
    if (fa[x] == x) return x;
    return fa[x] = find(fa[x]);
}

// 克鲁斯卡尔算法求最小生成树
int kruskal() {
    int ans = 0, cnt = 0;
    sort(edges, edges + m, [](Edge a, Edge b) { return a.w < b.w; }); // 按边权从小到大排序
    for (int i = 0; i < n; i++) fa[i] = i; // 初始化并查集
    for (int i = 0; i < m; i++) {
        int u = edges[i].u, v = edges[i].v, w = edges[i].w;
        int x = find(u), y = find(v);
        if (x != y) { // 如果u和v不在同一个连通块中
            fa[x] = y; // 合并u和v所在的连通块
            ans += w; // 加上边权
            cnt++; // 计数器加1
            if (cnt == n - 1) break; // 边数达到n-1，结束循环
        }
    }
    return ans;
}

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

程序中用到了并查集来实现判断两个节点是否在同一个连通块中，可以有效地减少程序的时间复杂度，使其达到O(mlogm)。