克鲁斯卡尔算法构造最小生成树，c

克鲁斯卡尔算法是一种贪心算法，用于构造加权无向图的最小生成树。其主要思路是从小到大地选取边，直至构成一棵生成树。具体实现步骤如下：
1. 将所有边按照权值从小到大排序；
2. 依次考虑每一条边，若该边的两个端点不在同一连通块中，则将这条边加入最小生成树，并将这两个端点所在的连通块合并为一个连通块；
3. 重复第二步，直至最小生成树中包含n-1条边，其中n为图中的节点数。

以下是C++实现代码：

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

const int MAXN = 10005, MAXM = 100005;

struct Edge {
    int u, v, w;
    bool operator<(const Edge& e) const {
        return w < e.w;
    }
} edges[MAXM];

int fa[MAXN];

int find(int x) {
    return fa[x] == x ? x : fa[x] = find(fa[x]);
}

int main() {
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= n; ++i) {
        fa[i] = i;
    }
    for (int i = 0; i < m; ++i) {
        cin >> edges[i].u >> edges[i].v >> edges[i].w;
    }
    sort(edges, edges + m);
    int cnt = 0, ans = 0;
    for (int i = 0; i < m; ++i) {
        int u = edges[i].u, v = edges[i].v, w = edges[i].w;
        int fu = find(u), fv = find(v);
        if (fu != fv) {
            fa[fu] = fv;
            ans += w;
            ++cnt;
            if (cnt == n - 1) {
                break;
            }
        }
    }
    cout << ans << endl;
    return 0;
}