克鲁斯卡尔算法最小生成树c++

克鲁斯卡尔算法是一种用于构建最小生成树的贪心算法。它的思想是先将图中所有的边按照权值从小到大排序，然后从小到大依次选取每条边，如果这条边连接的两个顶点不在同一个连通块中，则将这两个连通块合并成一个。

C++代码如下：

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5, M = 1e6 + 5;
int n, m;
int p[N];
struct Edge {
    int u, v, w;
} e[M];
int find(int x) {
    if (p[x] != x) p[x] = find(p[x]);
    return p[x];
}
void merge(int x, int y) {
    p[find(x)] = find(y);
}
int kruskal() {
    sort(e + 1, e + m + 1, [](Edge a, Edge b) {return a.w < b.w;});
    for (int i = 1; i <= n; ++i) p[i] = i;
    int res = 0;
    for (int i = 1; i <= m; ++i) {
        int u = e[i].u, v = e[i].v, w = e[i].w;
        if (find(u) == find(v)) continue;
        merge(u, v);
        res += w;
    }
    return res;
}
int main() {
    cin >> n >> m;
    for (int i = 1; i <= m; ++i) cin >> e[i].u >> e[i].v >> e[i].w;
    cout << kruskal() << endl;
    return 0;
}