【笔记】Borůvka's Algorithm

Borůvka 算法是一种计算图最小生成树的贪心算法，于 1926 年被 Otakar Borůvka 首次发表。

基本原理

首先，我们会找到图上每个节点到其他节点的最短边，然后把这些边加入森林中。我们不断重复这个过程，即每次给森林中每棵树找到连接其他树的最短边，然后将这样的边加入森林。

每次操作会减少森林中树的数量至少一半，于是我们可以在对数次操作内完成这个算法。

均摊复杂度为 $\Theta((n+m)\log n)$。

典型例题

对于大多数的图，Kruskal 和 Prim 已经非常优秀了。这里我们给出一个特殊情况，在这种情况下 Borůvka 的效率比前两者高得多。

给定 $n$ 个二维平面内的点，两点之间边权为两点的曼哈顿距离，求这些点的最大生成树大小。

在这里，图中边的数量达到了 $n^2$ 级别，不适宜直接计算。

因为边权是曼哈顿距离，我们发现我们可以较快地算出对于每棵树，到它距离最远的点的距离，Borůvka 算法可以在 $\Theta(n\log^2 n)$ 内完成。其中，每次操作会访问 $n$ 个点，查询距离的复杂度为 $\log n$。

代码

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn=1e5+5;
const int dx[]={1,-1,1,-1};
const int dy[]={-1,-1,1,1};

int read(){
    int x=0,flag=1;char ch=getchar();
    while(!isdigit(ch)&&ch!='-') ch=getchar();
    if (ch=='-') flag=-1,ch=getchar();
    while(isdigit(ch)) x=(x<<3)+(x<<1)+ch-'0',ch=getchar();
    return x*flag;
}

set<pair<ll,int>>S[maxn];
int n,cnt;
int x[maxn],y[maxn],fa[maxn];
ll ans,a[maxn][4];
vector<int>g[maxn];

struct Edge{
    int u,v,w;
    Edge(int a=0,int b=0,int c=0){
        u=a,v=b,w=c;
    }
}e[maxn];

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

bool merge(int x,int y){
    int fx=find(x),fy=find(y);
    if (fx==fy) return 0;
    if (g[fx].size()>g[fy].size()) swap(fx,fy);
    for (int i=0;i<g[fx].size();++i) g[fy].push_back(g[fx][i]);
    g[fx].clear();fa[fx]=fy;return 1;
}

void come_out(){
    printf("%lld\n",ans);
    exit(0);
}

int main(){
    n=read();
    for (int i=1;i<=n;++i)
    x[i]=read(),y[i]=read(),
    fa[i]=i,g[i].push_back(i);
    for (int i=1;i<=n;++i)
        for (int j=0;j<4;++j)
        S[j].insert(make_pair(a[i][j]=x[i]*dx[j]+y[i]*dy[j],i));
    while(true){
        cnt=0;
        for (int i=1;i<=n;++i) if (fa[i]==i){
            if (g[i].size()==n) come_out();
            for (int j=0;j<g[i].size();++j)
                for (int k=0;k<4;++k)
                S[k].erase(make_pair(a[g[i][j]][k],g[i][j]));
            ll mx=-1ll<<40,v;
            for (int k=0;k<4;++k){
                ll mx1=-1ll<<40,mx2;
                for (int j=0;j<g[i].size();++j)
                if (a[g[i][j]][k]>=mx1) mx1=a[g[i][j]][k];
                set<pair<ll,int>>::iterator it=S[k^3].end();
                it--;mx2=it->first;
                if (mx1+mx2>=mx) mx=mx1+mx2,v=it->second;
            }
            e[++cnt]=Edge(i,v,mx);
            for (int j=0;j<g[i].size();++j)
                for (int k=0;k<4;++k)
                S[k].insert(make_pair(a[g[i][j]][k],g[i][j]));
        }
        for (int i=1;i<=cnt;++i)
            if (merge(e[i].u,e[i].v)) ans+=e[i].w;
    }
    return 0;
}