[编程笔记]-Kruskal

作用

多在稀疏图中生成最小生成树

实现

1. 将每条边从小到大排好序。
2. 找到一条连接两个不同集合的边权最小的边，将其加入确定的边中。
3. 重复n-1次，即所有点都加入了最小生成树。

特殊地，判断连接的是否是两个不同集合，推荐使用并查集。
[编程笔记]-Union_Find_Set并查集

代码

#include<bits/stdc++.h>
using namespace std;

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

class ufset{
    public:
        int n;
        int p[N];
        void init(int x){
            n=x;
            for(int i=1;i<=n;i++){
                p[i]=i;
            }
        }
        int find(int x){
            if(p[x]!=x)p[x]=find(p[x]);
            return p[x];
        }
        void merge(int a,int b){
            a=find(a);b=find(b);
            p[a]=b;
        }
        bool same(int a,int b){
            return find(a)==find(b);
        }
}ufs;

struct edge{
    int u,v,w;
}es[M];

int n,m;

bool cmp(edge a,edge b){
    return a.w<b.w;
}

void kruskal(){
    sort(es+1,es+1+m,cmp);
    ufs.init(n);
    int fns=0,res=0;
    for(int i=1;i<=m;i++){
        while(i<=m&&ufs.same(es[i].u,es[i].v))i++;
        if(i>m)break;
        ufs.merge(es[i].u,es[i].v);
        fns++;
        res+=es[i].w;
    }
    if(fns==n-1)cout<<res;
    else cout<<"impossible";
}

int main(){
    cin>>n>>m;
    for(int i=1;i<=m;i++){
        cin>>es[i].u>>es[i].v>>es[i].w;
    }
    kruskal();
    return 0;
}

完结撒花o(￣︶￣)o