最小生成树

Reference

https://oi.wiki/graph/mst

前置知识

生成树是连接无向图中所有点且边数最少的连通子图
最小生成树是边权和最小的生成树
且对于一棵边权互不相等的树，其最小生成数只有一棵

Kruskal

（自写，求轻喷

#include<iostream>
#include<numeric>
#include<algorithm>
#define N 1000001
using namespace std;

struct edge{
    int u,v,w;
    bool operator <(const edge &x) const {
        return w<x.w;
    }
}e[N];
struct DSU{
    int fa[N];
    DSU(){iota(fa,fa+N,0);}
    inline void insert(int pa,int x){
        fa[x]=pa;
    }
    inline int find(int x){
        return x==fa[x]?x:(fa[x]=find(fa[x])); 
    }
}dsu;

int main(){
    int n,m;
    scanf("%d %d",&n,&m);
    for(int i=1;i<=m;++i){
        scanf("%d %d %d",&e[i].u,&e[i].v,&e[i].w);
    }
    sort(e+1,e+1+m);
    int ans=0,cnt=0;
    for(int i=1;i<=m;++i){
        int eu=dsu.find(e[i].u),ev=dsu.find(e[i].v);
        if(eu==ev) continue;//  两点联通
        ans+=e[i].w;
        dsu.insert(eu,ev);
        ++cnt;
        if(cnt==n-1) break;
    }
    printf("%d",ans);
}

在使用 $\Theta(mlogm)$ 的排序算法和 $\Theta(m\alpha(m,n))$ 或 $\Theta(mlogn)$ 的并查集时， 时间复杂度可以做到 $\Theta(mlogm)$ \

解释：将边按权排序，维护一个森林，按照权值大小取边，如果边连着的两点在森林里有同一个父亲，那就意味着成环，所以舍弃，否则将两点添加到森林（但并查集的时候已经添了啊qaq）