Brouvka算法

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+50,maxm=2e5+5;
const int MaxN = 5000 + 5, MaxM = 200000 + 5;
int N, M;
int U[MaxM], V[MaxM], W[MaxM],Best[maxn];
bool used[MaxM];
int  father[maxn];
void init(int n)
{
	for(int i=1;i<=n;i++)
	    father[i]=i;
}
int find(int x){return x==father[x]?x:father[x]=find(father[x]);}
void unionSet(int x,int y)
{
        int xx=find(x),yy=find(y);
        if(xx==yy) return;
        father[xx]=yy;
}
inline bool Better(int x, int y)
{
    if (y == 0) return true;
    if (W[x] != W[y])
         return W[x] < W[y];
    return x < y;
}

void Boruvka() 
{
    init(N);
    int merged = 0, sum = 0;
    bool update = true;
    while (update)
    {
        update = false;
        memset(Best, 0, sizeof Best);
        //将每个点集清空 
        for (int i = 1; i <= M; ++i)
        //枚举所有的边 
        {
            if (used[i] == true) 
            //如果这个边已在MST中，就不管 
			   continue;
            int p = find(U[i]), q = find(V[i]);
            //看边的两个点，分别在哪个集合 
            if (p == q) 
			    continue;
            if (Better(i, Best[p]) == true)
            //看下第i条边的长度，是否比p这个集合伸出来的边，要更优 
                 Best[p] = i;
            if (Better(i, Best[q]) == true)
                Best[q] = i;
        }
        for (int i = 1; i <= N; ++i)
        //枚举所有的点集 
            if (Best[i] != 0 && used[Best[i]] == false)
            //如果这个点集有边伸出来了，并且这条边没在MST中 
            {
                update = true;
                //说明有更新操作 
                merged++;
                //加了多少条边 
                sum += W[Best[i]];
                //代价加起来 
                used[Best[i]] = true;
                //这个边在MST中 
                unionSet(U[Best[i]],V[Best[i]]);
                //把这两个集合合并 
            }
    }

    if (merged == N - 1)
         printf("%d\n", sum);
    else
         puts("orz");
}

int main() {
    scanf("%d %d", &N, &M);
    for (int i = 1; i <= M; ++i)
        scanf("%d%d%d", &U[i], &V[i], &W[i]);
    Boruvka();
    return 0;
}