最小生成树——克鲁斯卡尔(Kruskal)算法

#include <iostream>
#include <algorithm>
#include <string.h>
#include <vector>
#include<cstdio>
using namespace std;

#define MAXV 10005
#define MAXE 100005

struct edge
{
    int from, to, weight;
} eg[4*MAXE];

int v, e;
int head[MAXV] = {0};
int js_edges = 0;
int fa[MAXV] = {0};//并查集
int Rank[MAXV] = {0};

bool cmp(const edge &a,const edge &b)
{
    return a.weight<b.weight;
}


void add_edges(int s,int t,int w)
{
    
    eg[js_edges].from = s;
    eg[js_edges].to =t;
    eg[js_edges].weight = w;
    
    js_edges++;
}

int find_set(int i)
{
    if(fa[i]==i) return i;

    fa[i] = find_set(fa[i]);
    return fa[i];
}

void unite(int x,int y)
{
    int fx = find_set(x);
    int fy = find_set(y);

    if(Rank[fx]>Rank[fy])
    {
        fa[fy] = fx;
    }
    else
    {
        fa[fx] = fy;
        if(Rank[fx]==Rank[fy])
            Rank[fy]++;
    }
}


int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    cin >> v >> e;

    int s, t, w;
    for (int i = 0; i < e; ++i)
    {
        cin >> s >> t >> w;
        add_edges(s,t,w);
        //add_edges(t,s,w);
    }

    sort(eg,eg+js_edges,cmp);//把边的权值按照升序排列

    for(int i=0;i<=v;++i)//初始化并查集
        fa[i] = i;
    
    long long ans=0;

    for(int i=0;i<js_edges;++i)
    {
        if(find_set(eg[i].from)!=find_set(eg[i].to))
        {
            unite(eg[i].from,eg[i].to);
            ans+=eg[i].weight;
            //可以在这里把边加入最小生成树。
        }
    }

    cout<<ans<<endl;
}