洛谷——最小生成树模板

https://www.luogu.org/problemnew/show/P3366

#include <cstdio>
#include <algorithm> 
using namespace std;
const int maxn = 2000005; 
const int maxx = 5005;
int root[maxx];
int find(int x){
    return x==root[x]?x:root[x]=find(root[x]);
}
struct edge{
    int u,v;
    int cost;
    bool operator <(const edge &b)const{
        return cost < b.cost;
    }
}E[maxn];
int main(){
    int N,M;
    scanf("%d%d",&N,&M);
    for(int i = 0; i < M; i++){
        scanf("%d%d%d",&E[i].u,&E[i].v,&E[i].cost);
    }
    sort(E,E+M);
    for(int i = 1;i <= N; i++){
        root[i] = i;
    }
    int total = 0;
    for(int i=0;i<M;i++){
        int faU = find(E[i].u);
        int faV = find(E[i].v);
        if(faU != faV){
            root[faU] = faV;
            total += E[i].cost;
        } 
    }
    printf("%d\n",total);
    return 0;
}