Boruvka算法求最小生成树
算法的核心思想是贪心，类似于 \(kruskal\)
算法过程：
- 维护途中所有联通块，然后遍历所有点和边。
- 找到每一个联通块和其他联通块相连的最小的一条边。
- 把连通块合并起来，重复操作，直到剩下一整个连通块。
复杂度分析：
复杂度是 \(O((m+n)log n)\) ,每次合并两个连通块，进行 \(log\) 次就能完成。
代码：
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int nxt[N],ver[N],tot,edge[N],head[N];
int n,m,fa[N],mn[2][N],ans;
/*
mn第一维存fx这个节点距离其他节点最小的长度
第二维存当前连通块的缩点的点
*/
void add(int x,int y,int z){
ver[++tot]=y; edge[tot]=z; nxt[tot]=head[x]; head[x]=tot;
}
int get(int x){
if(x==fa[x]) return x;
else return fa[x]=get(fa[x]);
}
void merge(int x,int y){
int fx=get(x),fy=get(fy); fa[fx]=fy;
}
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++) fa[i]=i;
for(int i=1,x,y,z;i<=m;i++){
scanf("%d%d%d",&x,&y,&z); add(x,y,z); add(y,x,z);
}
while(1){
memset(mn[0],127,sizeof(mn[0])); bool flag=0;
for(int x=1;x<=n;x++)
for(int i=head[x];i;i=nxt[i]){
int y=ver[i],fx=get(x),fy=get(y);
if(fx==fy) continue;
if(mn[0][fx]>edge[i]){
mn[0][fx]=edge[i];
mn[1][fx]=fy;
}
}
for(int i=1;i<=n;i++)
if(mn[0][i]!=mn[0][0]&&get(i)!=get(mn[1][i]))
flag=1,ans+=mn[0][i],merge(i,mn[1][i]);
if(!flag) break;
}
for(int i=1;i<n;i++) if(get(i)!=get(i+1)){
puts("NO"); return 0;
}
cout<<ans<<endl;
return 0;
}