Borůvka算法学习小记

概述

Borůvka算法是一种求 \(\text{MST}\) 的 \(n \log n\) 算法 （ \(\text{prim}\space m + n \log n (\text{Fib 堆优化}), \text{kruskal}\space m \log n\) )

思想

可以将其看成多源化的 \(\text{prim}\) 算法

伪代码如下

一开始图中每一个都是一个单独的联通块

当标记为真时：

标记更新为假

对于每一条不在 \(\text{MST}\)上的，连接两个联通块的边 \(\text{u,v}\)（并查集维护）：

    如果 len(u, v) 比拓展（指将该联通块连接到另一个联通块上）u 所在联通块的原花费要小，则用前者更新后者
   
    对于 v 所在联通块也是如此
    

对于每一个联通块：

        如果记录的最小花费被更新过，且该记录未被用过（为了防止一条边被重复更新）：
        
            标记更新为真
            
            联通块个数-1，答案+=花费
            
                将该边标记为已用，合并这条边连接的两个联通块
            
            

主函数内：

如果联通块个数为1，则该图联通

代码

#include <bits/stdc++.h>
using namespace std;
const int maxn = 5000 + 10, maxm = 200000 + 10;
int n, m, fa[maxn], best[maxn], cnt, ans, used[maxm];
struct edge { int fr, to, w; } e[maxm];
int gf(int x) { return fa[x] == x ? fa[x] : fa[x] = gf(fa[x]); }
void init(int n) { for (int i = 1; i <= n; ++i) fa[i] = i; }
void mer(int a, int b) { if (gf(a) != gf(b)) fa[gf(b)] = gf(a); }
void boruvka() {
    bool flg = true;
    while (flg) {
        flg = false;
        memset(best, 0, sizeof best);
        for (int i = 1; i <= m; ++i) {
            if (gf(e[i].fr) != gf(e[i].to) && !used[i]) {
                int fa = gf(e[i].fr), fb = gf(e[i].to);
                if (e[i].w < e[best[fa]].w) best[fa] = i;
                if (e[i].w < e[best[fb]].w) best[fb] = i;
            }
        }
        for (int i = 1; i <= n; ++i) {
            if (best[i] != 0 && !used[best[i]]) {
                flg = true; cnt ++, ans += e[best[i]].w;
                used[best[i]] = true, mer(e[best[i]].fr, e[best[i]].to);
            }
        }
    }
}
int main() {
    scanf("%d %d", &n, &m); init(n); e[0].w = 0x7fffffff;
    for (int i = 1; i <= m; ++i) scanf("%d %d %d", &e[i].fr, &e[i].to, &e[i].w);
    boruvka();
    if (cnt == n - 1) printf("%d", ans);
    else puts("orz");
    return 0;
}