Kruskal算法求最小生成树

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

const int N = 200020;
int p[N];
int n, m;

struct Edge {
    int a, b, w;
    bool operator< (const Edge &W) const { // 重载<
        return w < W.w;
    }
} edges[N];

int find(int x) {  // 并查集操作
    if(p[x] != x) p[x] = find(p[x]);
    return p[x];
}

int main() {
    scanf("%d%d",&n,&m);
    for(int i = 1; i <= n; i++) p[i] = i; // 初始化并查集
    for(int i = 0; i < m; i++) {
        int a, b, c;
        scanf("%d%d%d",&a,&b,&c);
        edges[i] = {a,b,c};
    }
    sort(edges,edges+m);
    int res = 0, cnt = 0;
    for(int i = 0; i < m; i++) {
        int a = edges[i].a, b = edges[i].b, w = edges[i].w;
        int fa = find(a), fb = find(b);
        if(fa != fb) {
            res += w;
            cnt++;
            p[fa] = fb;
        }
    }
    if(cnt < n -1) puts("impossible");
    else printf("%d
",res);
    return 0;
    
}