基于并查集实现的最小生成树算法，贪心选取最短的边，如果这条边连接的两个节点不在同一集合内，那就加入树

查询是否在同一集合已经合并集合的操作通过并查集实现

#include<bits/stdc++.h>

using namespace std;

struct edge{
    int u,v,w;
};

vector<edge> e;
int n,m;
int fa[5010];
int cnt,sum;

int find(int x){
    if (x==fa)
        return x;
    return fa=find(fa);
}

bool kruskal(void){
    for (int i=0;i<=n;i++) fa[i]=i;
    sort(e.begin(),e.end(),[](edge x,edge y){return x.w<y.w;});
    for (auto [u,v,w]:e){
        int x=find(u),y=find(v);
        if (x!=y){
            cnt++;
            sum+=w;
            fa=y;
        }
    }
    return cnt==n-1;
}

int main()
{
    cin>>n>>m;
    
    int u,v,w;
    for (int i=1;i<=m;i++){
        cin>>u>>v>>w;
        e.push_back({u,v,w});
    }
    bool f=kruskal();
    if (f) cout<<sum;
    else cout<<"orz";
    return 0;
}

算法开始时，将每个节点的祖先节点初始化为自己

对每条边按照边权排序后从小到大遍历，如果这条边连接的两个节点的祖先不同，那么就将这两个节点所在的集合进行合并

查询祖先节点时，使用路径压缩优化，因为我们只需要求解最短路，和并查集内部的结构无关

合并两个节点后，树内的节点数 $+1$ ，累加总边权

最后返回树内的节点数是否等于总节点数$-1$ ，如果相等，说明所有的点都可连通，最小生成树存在