算法2

kruskal最小生成树

参考文献

acwing 算法基础课
首先明确一点，kruskal算法是基于贪心的思想，就是将当前的边权排序，每次选取权值最小的，然后判断这个边连接的两个点是否已经在一个块里，如果在，则continue;如果不在，res+=w[i],同时开一个计数器，记录一下加进去的边的个数
直到cnt-1，然后退出，如果cnt==n-1说明最小生成树已经成功生成，反之，无法生成。

C++ 代码

#include<bits/stdc++.h>
using namespace std;
const int M=3e5;
int res=0;
int n,m;
struct node{
    int a,b,w;
    bool operator <(const node W)const 
    {
        return w<W.w;
    }
}e[M];
int fa[M];
int find(int x)
{
    if(x==fa[x])
        return fa[x];
    return fa[x]=find(fa[x]);
}

int kruskal()
{
    int cnt=0;
    sort(e+1,e+1+m);
    for(int i=1;i<=m;i++)
    {
        int a=e[i].a;
        int b=e[i].b;
        if(find(a)!=find(b))
        {   
            fa[find(a)]=find(b);
            res+=e[i].w;
            cnt++;
        }
        if(cnt==n-1)
        return 1;
    }
    return 0;
}
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
        fa[i]=i;
    for(int i=1;i<=m;i++)
    {
        int a,b,c;
        cin>>a>>b>>c;
        e[i]={a,b,c};
    }

    if(kruskal()==1)
    cout<<res<<endl; else cout<<"impossible"<<endl;

    return 0;
}