【最小生成树】Kurskal算法

Kurskal算法，从小到大加入边（贪心思想），需要用到并查集来避免形成回路。模板如下：

struct Kurskal{
    struct Edge{
        int u,v,len;
        bool operator < (const Edge &e) const{
            return len<e.len;
        }
    };
    int n,m;//节点数，边数
    vector<Edge> edges;
    vector<int> fa;
    Kurskal(int n,int m) : n(n),m(m),fa(n+1) {
        for(int i=1;i<=n;++i) fa[i]=i;
    }
    void addEdge(int u,int v,int len){
        edges.push_back({u,v,len});
    }
    int fnd(int x){
        if(fa[x]!=x) fa[x]=fnd(fa[x]);
        return fa[x];
    }
    bool merge(int x,int y){
        int fx=fnd(x),fy=fnd(y);//在同一个集合，表示这两点已经联通
        if(fx==fy) return false;//再加边就会形成回路
        fa[fy]=fx;
        return true;
    }
    int run(){
        sort(edges.begin(),edges.end());
        int ans=0,cnt=0;
        for(int i=0;i<m;++i){
            if(merge(edges[i].u,edges[i].v)){
                ans+=edges[i].len;
                cnt++;
            }
            if(cnt==n-1) break;
        }
        if(cnt==n-1) return ans;
        return -1;//没有找到最小生成树
    }
};

模板题：洛谷P3366 【模板】最小生成树

#include <bits/stdc++.h>
using namespace std;
struct Kurskal{
    struct Edge{
        int u,v,len;
        bool operator < (const Edge &e) const{
            return len<e.len;
        }
    };
    int n,m;//节点数，边数
    vector<Edge> edges;
    vector<int> fa;
    Kurskal(int n,int m) : n(n),m(m),fa(n+1) {
        for(int i=1;i<=n;++i) fa[i]=i;
    }
    void addEdge(int u,int v,int len){
        edges.push_back({u,v,len});
    }
    int fnd(int x){
        if(fa[x]!=x) fa[x]=fnd(fa[x]);
        return fa[x];
    }
    bool merge(int x,int y){
        int fx=fnd(x),fy=fnd(y);//在同一个集合，表示这两点已经联通
        if(fx==fy) return false;//再加边就会形成回路
        fa[fy]=fx;
        return true;
    }
    int run(){
        sort(edges.begin(),edges.end());
        int ans=0,cnt=0;
        for(int i=0;i<m;++i){
            if(merge(edges[i].u,edges[i].v)){
                ans+=edges[i].len;
                cnt++;
            }
            if(cnt==n-1) break;
        }
        if(cnt==n-1) return ans;
        return -1;//没有找到最小生成树
    }
};
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n,m;
    cin>>n>>m;
    Kurskal kurs(n,m);
    for(int i=0;i<m;++i){
        int u,v,w;
        cin>>u>>v>>w;
        kurs.addEdge(u,v,w);
    }
    int ans=kurs.run();
    if(ans!=-1) cout<<ans;
    else cout<<"orz";
	return 0;
}