AcWing 859. Kruskal算法求最小生成树

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

int n, m;
struct Edge {
    int u, v, w;
    bool operator < (const Edge &x) {
        return w < x.w; 
    }
} g[200005];

int fa[100005];
int find(int x) {
    if (fa[x] == x) return x;
    return fa[x] = find(fa[x]);
}

int main() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) fa[i] = i;
    for (int i = 1; i <= m; i++) cin >> g[i].u >> g[i].v >> g[i].w;
    sort(g + 1, g + m + 1);
    int cnt = 0, s = 0;
    for (int i = 1; i <= m; i++) {
        if (cnt == n - 1) break;
        int u = g[i].u, v = g[i].v, w = g[i].w;
        int av = find(v), au = find(u);
        if (av == au) continue;
        cnt++, s += w;
        fa[av] = au;
    }
    if (cnt != n - 1) puts("impossible");
    else cout << s;
    return 0;
}