Kruskal最小生成树

#include <bits/stdc++.h>
using namespace std;

#define maxn 1000

int n,m;
struct edge{
    int u,v,w;
}e[maxn];

bool cmp(edge a,edge b){
    return a.w<b.w;
}

int ans;

//并查集
int s[maxn];
int find_set(int x){return x==s[x]?x:s[x]=find_set(s[x]);}

void kruskal(){
    iota(s,s+n+1,0);//初始化并查集
    sort(e,e+m,cmp);//排序

    int cnt(0);
    for(int i=0;i<m;++i){
        int x = find_set(e[i].u);
        int y = find_set(e[i].v);
        if(x==y) continue;
        s[y] = x;
        ans+=e[i].w;
        if(++cnt == n-1) break;
    }
}

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

本文地址：https://blog.csdn.net/weixin_45826022/article/details/109257469