洛谷题单 最小生成树1

洛谷题单<最小生成树> 直接上代码

#include<bits/stdc++.h>
using namespace std;//prim  kruskal 都可以做； 
const int N = 5010, M = 200010;

struct edge{
    int a, b, c;
    bool operator<(const edge& w)const{
        return c < w.c;
    }
}edges[M];

int n, m, p[N], cnt; //并查集； 

int find(int x){//并查集 压缩路径基本操作 
    if(x != p[x]) return p[x] = find(p[x]);
    else return x;
} 

int kruskal(){
    for(int i = 0; i <= n; i++) p[i] = i; // 初始化并查集
    sort(edges, edges + m); //边排序；
    int res = 0;
    for(int i = 0; i < m; i++){
        int a = edges[i].a, b = edges[i].b, c = edges[i].c;
        int x = find(a), y = find(b);

        if(x != y){
            p[x] = y;
            res += c;
            cnt ++;
        }
    } 
    if(cnt == n - 1) return res;
    else return -1;
}

int main(){
    cin >> n>> m;
    for(int i = 0; i < m; i++){
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        edges[i] = {a, b, c};
    }

    int t = kruskal();

    if(t != -1){
        printf("%d\n", t);
    }else puts("orz");

    return 0;
}