$$Prim$$

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<iostream>
using namespace std;
const int N = 1e6 + 1;
const int INF = 0x3f3f3f3f;
struct node{
    int to, w, ne;
}e[N];
int head[N], idx = 0, dis[N], n, m, tot = 0, now = 1, ans = 0;
bool vis[N];
inline void add(int u, int v, int w){
    e[++idx].to = v;
    e[idx].w = w;
    e[idx].ne = head[u];
    head[u] = idx;
}
inline int prim(){
    for(int i =  2;i <= n;i ++) dis[i] = INF;
    for(int i = head[1]; i; i = e[i].ne) dis[e[i].to] = min(dis[e[i].to], e[i].w);
    while(++ tot < n){
        int minn = INF;
        vis[now] = 1;
        for(int i = 1;i <= n;i ++){
            if(!vis[i] && minn > dis[i]){
                minn = dis[i];
                now = i;
            }
        }
        ans += minn;
        for(int i = head[now]; i; i = e[i].ne){
            int v = e[i].to;
            if(dis[v] > e[i].w && !vis[v]) dis[v] = e[i].w;
        }
    }   
    return ans;
}
int main(){
    cin >> n >> m;
    for(int i = 1;i <= m;i ++){
        int u, v, w;
        cin >> u >> v >> w;
        add(u, v, w);
        add(v, u, w);
    }
    int t = prim();
    if(t >= INF) puts("orz");
    else cout << t << endl;
    return 0;
}

$$Kruskal$$

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 1;
struct node{
    int u, v, w;
}e[N];
int fa[N], n, m;
int find(int x){return fa[x] == x ? x : fa[x] = find(fa[x]);}
bool cmp(node a, node b){return a.w < b.w;}
int main(){
    cin >> n >> m;
    for(int i = 1;i <= n;i ++) fa[i] = i;
    for(int i = 1;i <= m;i ++) cin >> e[i].u >> e[i].v >> e[i].w;
    sort(e + 1, e + m + 1, cmp); // 基于贪心思想，按边排序
    int cnt = 0, ans = 0;
    for(int i = 1;i <= m;i ++){ // Kruskal 模板
        int x = find(e[i].u);
        int y = find(e[i].v);
        if(x == y) continue;
        fa[x] = y;
        ans += e[i].w;
        cnt ++;
        if(cnt == n - 1) break;
    }
    if(cnt < n - 1) puts("impossible");// 连通的点小于n - 1个，即构不成最小生成树；
    else cout << ans << endl;
    return 0;
}