kruskal求最小生成树

1. 自定义边结构体，重载<
2. 并查集确定点是否在一个连通块中
3. 依次扫描每一个边，直到所有点节点均在一颗树中，即最小生成树，否则不存在。

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 100010, M = 2 * N;
struct edge {
    int s, e, v;
    bool operator< (const edge &a) const {
        return this->v < a.v;
    }
} ed[M];
int n, m;
int f[N], res, already = 1;

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

bool kruskal() {
    for (int i = 0; i < m; i++) {
        int s = find(ed[i].s), e = find(ed[i].e);
        if (s != e) {
            res += ed[i].v;
            already++;
            f[s] = e;
            if (already == n) return true;
        }
    }
    return false;
}

int main() {
    cin >> n >> m;
    for (int i = 0; i < m; i++) {
        cin >> ed[i].s >> ed[i].e >> ed[i].v;
    }
    sort(ed, ed + m);
    for (int i = 1; i <= n; i++) f[i] = i;
    if (kruskal()) cout << res << endl;
    else cout << "impossible" << endl;

    return 0;
}