859 Kruskal求最小生成树

把所有边按照权重值从小到大排序，然后一一收入集合，利用联通集判断一条边的两个点是否在一个联通集中 如果在就不收录这条边

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

const int N = 100010, M = 200010;
int n, m;
int P[N];
struct edge{
    int a, b, w;
    bool operator< (edge &e) const{
        return w < e.w;
    }
}edges[M];

int find(int x) {
    if (P[x] != x) P[x] = find(P[x]);
    return P[x];
}

int main() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) P[i] = i;
    for (int i = 0; i < m; i++) {
        int a, b, w;
        cin >> a >> b >> w;
        edges[i] = {a, b, w};
    }
    sort(edges, edges + m);
    
    int res = 0, cnt = 1;
    for (int i = 0; i < m; i++) {
        int a = edges[i].a, b = edges[i].b, w = edges[i].w;
        a = find(a), b = find(b);
        if (a == b) continue;
        else {
            res += w;
            P[a] = b;
            cnt ++;
        }
    }
    if (cnt < n) puts("impossible");
    else cout << res;
    return 0;
}