859.Kruskal最小生成树

tip

原题链接：https://www.acwing.com/problem/content/861/

思路

从原本算法入手，Kruskal算法是从添加边的角度出发，适合求稀疏图的最小生成树。也就是将边权最小的点的加入到集合当中，所以可以想到思路是：

• 按照边权将边排序（升序）
• 按照边权从小到大选择边，每一条边所连接的两个点可以表示一个集合，当两条边上的节点要相连时，本质上就是集合合并问题。假设：1，3 节点所连接的边和 2，4 所连接的边。当前需要将 2 和 3 连接起来，相当于就是集合{1,3}和集合{2,4}要进行合并，所以可以使用并查集进行合并。

代码

#include <bits/stdc++.h>

using namespace std;

const int N = 1e5 + 10, M = 2e5 + 10;

int p[N];

int n, m;

struct Edge {
    int u;
    int v;
    int w;
    
    bool operator< (const Edge &E) const {
        return w < E.w;
    }
} e[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++) {
        cin >> e[i].u >> e[i].v >> e[i].w; 
    }
    sort(e, e + m);
    
    int res = 0, cnt = 0;
    for (int i = 0; i < m; i++) {
        int u = e[i].u, v = e[i].v, w = e[i].w;
        u = find(u), v = find(v);
        if (u != v) {
            p[u] = v;
            res += w;
            cnt ++;
        }
    }
    if (cnt < n -1) cout << "impossible" << endl;
    else cout << res << endl;
    
    return 0;
}