$\huge \color{orange}{成仙之路->}$ $\huge \color{purple}{算法基础课题解}$

思路：

1. 将每条边从小到大排序
2. 枚举每条边，如果不在一个集合就合并集合
3. res 表示最小生成树权重之和
4. cnt 表示已加入集合的边数

完整代码 $O(mlogm)$

#include<bits/stdc++.h>

using namespace std;

const int N = 100010, M = N * 2;

int n,m;
int p[N];

struct Edge
{
    int a,b,w;
    bool operator< (const Edge &t) const
    {
        return w<t.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=0;i<m;i++)
    {
        int a,b,w;
        cin>>a>>b>>w;
        edges[i]={a,b,w};
    }

    //排序
    sort(edges,edges+m);

    //并查集初始化
    for(int i=1;i<=n;i++) p[i]=i;

    //res表示最小生成树权重之和，cnt表示边数
    int res=0,cnt=0;

    //枚举每一条边
    for(int i=0;i<m;i++)
    {
        int a=find(edges[i].a),b=find(edges[i].b),w=edges[i].w;

        //如果两个点不在同一个连通块中就合并集合
        if(a!=b)
        {
            p[a]=b;
            res+=w;
            cnt++;
        }
    }

    if(cnt<n-1) cout<<"impossible"<<endl;
    else cout<<res<<endl;

    return 0;
}