标准的克鲁斯卡尔算法（借助并查集的思想）

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 100010, M = 2*N; //注意是无向图，M=2*N
int p[N];  //并查集
struct Edge
{
    int a,b,w;
}edge[M];  //结构体存储每条边的两个节点和权重
bool cmp(Edge&A,Edge&B)  //重写cmp函数，便于结构体内部排序
{
    return A.w<B.w;
}
int find(int x) //并查集板子
{
    if (p[x]!=x) p[x]=find(p[x]);
    return p[x];
}
int main()
{
    int n,m;
    scanf("%d%d",&n,&m);
    for (int i=0;i<m;i++)
    {
        int a,b,w;
        scanf("%d%d%d",&a,&b,&w);
        edge[i]={a,b,w};
    }

    for (int i=1;i<=n;i++) p[i]=i;  //初始并查集，每个节点是独立的，根节点是自己

    sort(edge,edge+m,cmp);  //边按照权重递增排序

    int sum=0,cnt=0;  //sum表示最小生成树的权重，cnt表示最小生成树的边数
    for (int i=0;i<m;i++)
    {
        int a=edge[i].a,b=edge[i].b,w=edge[i].w;
        if (find(a)!=find(b)) //如果a和b不是一个连通块，即a和b不连通，就连通即可
        {
            sum+=w;
            cnt++;
            p[find(a)]=find(b);
        }
    }
    if (cnt<n-1) puts("impossible");  //最小生成树的边数一定等于节点数-1，若不等则不连通
    else printf("%d\n",sum);
    return 0;
}