Borůvka (Sollin) 算法求 MST 最小生成树

基本思路：

用定点数组记录每个子树的最近邻居。

对于每一条边进行处理：

如果这条边连成的两个顶点同属于一个集合，则不处理，否则检测这条边连接的两个子树，如果是连接这两个子树的最小边，则更新 (合并)。

时间复杂度平均 \(O(V+E)\)，最坏 \(O((V+E)\log V)\)。

下面是 Borůvka 算法演示动图：（源：Wikimedia）

程序代码：

struct node {int x, y, w; } edge[M];

int d[N];   // 各子树的最小连外边的权值

int e[N];   // 各子树的最小连外边的索引

bool v[M];  // 防止边重复统计

int fa[N];

int find(int x) {return x==fa[x] ? x : (fa[x]=find(fa[x])); }

void join(int x, int y) {fa[find(x)]=find(y); }

int Boruvka() {

    int tot=0;

    for (int i=1; i<=n; ++i) fa[i]=i;

    while (true) {

        int cur=0;

        for (int i=1; i<=n; ++i) d[i]=inf;

        for (int i=1; i<=m; ++i) {

            int a=find(edge[i].x), b=find(edge[i].y), c=edge[i].w;

            if (a==b) continue;

            cur++;

            if (c<d[a] || c==d[a] && i<e[a]) d[a]=c, e[a]=i;

            if (c<d[b] || c==d[b] && i<e[b]) d[b]=c, e[b]=i;

        }

        if (cur==0) break;

        for (int i=1; i<=n; ++i) if (d[i]!=inf && !v[e[i]]) {

            join(edge[e[i]].x, edge[e[i]].y), tot+=edge[e[i]].w;

            v[e[i]]=true;

        }

    }

    return tot;

}