贪心最小生成树kruskal算法c++

以下是使用C++语言实现Kruskal算法的最小生成树代码：

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
const int N = 1001000;
struct edge{
    int u, v, w;
}e[N];
int fa[N], tot, n, m, ans;

void init(){
    for(int i=1; i<=n; i++)
        fa[i] = i;
}
int find(int x){
    if(x != fa[x])
        fa[x] = find(fa[x]);
    return fa[x];
}
void merge(int x, int y){
    int fx = find(x), fy = find(y);
    if(fx != fy)
        fa[fx] = fy;
}

bool cmp(edge x, edge y){
    return x.w < y.w;
}
int kruskal(){
    int cnt = 0, sum = 0;
    sort(e+1, e+m+1, cmp);
    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)){
            merge(u, v);
            cnt++;
            sum += w;
        }
        if(cnt == n-1) break;
    }
    if(cnt == n-1) return sum;
    else return -1;
}

int main(){
    scanf("%d%d", &n, &m);
    init();
    for(int i=1; i<=m; i++){
        int u, v, w;
        scanf("%d%d%d", &u, &v, &w);
        e[i].u = u;
        e[i].v = v;
        e[i].w = w;
    }
    ans = kruskal();
    printf("%d\n", ans);
    return 0;
}

该代码的实现基于并查集和Kruskal算法，可以求出一个连通图的最小生成树。其中，e[N]代表边，edge结构体中存储了每条边的起点、终点和权值。init()函数用于初始化并查集，find()函数用于查找某个元素所在的集合，merge()函数用于合并两个集合。kruskal()函数则是实现Kruskal算法的核心，通过对边权值从小到大排序，不断选取权值最小的边进行合并，并判断是否形成环即可。最终返回最小生成树的权值和。

注意：该算法对于非连通图，会输出-1。如果需要应对该问题，可以增加一个记录连通块个数的变量，当连通块个数为1时，不需要继续进行合并操作。