Borůvka算法是一种多路Prim最小生成树算法，其复杂度为\(m\log n\)，但不如Kruskal的\(\log\)。其主要功能是用于求解简单图的最小生成树。

算法流程如下：首先考虑当前的图（未连边），它一定由若干连通块构成，然后考虑连接这些连通块。对于任意一个连通块，在本操作中，应该与尽可能优的连通块连边。如果该连通块不在本操作连边，无论以后的操作如何改变其他连通块的状态，连通块总是单调不减的，花费也一定是单调不减的。根据上述原理，可以尝试枚举所有边，然后尝试用这条边去更新端点所在连通块，对于连通块，则选择一个最优的边来更新自身。在一次操作中，总有至少一半的连通块被连接而消失，因此复杂度为\(m\log n\)。

在使用Borůvka算法时需要注意以下几点：首先，需要保证“最优的边”是严格的，即不存在\(i,j\in [1,m]\)，使得两条边\(e_i=e_j\)。另外，需要在无向图上跑最小生成树时判定是否连出环。Borůvka算法需要判定的东西比较多，需要注意不要漏掉。

P3366 【模板】最小生成树

#include<bits/stdc++.h>
using namespace std;
// ...（代码详见原文）

显然，Borůvka在稠密图上的表现不如Prim，在稀疏图上的表现不如Kruskal。然而，Borůvka适用于一类特殊条件，例如给定一个完全图，完全图上的边权可以通过端点的点权经过某种计算得出，求最小生成树。这样的条件充分利用了Borůvka只会合并\(\log n\)次的性质，这是其他两个最小生成树算法做不到的。但是，这并不意味着套用模板就可以了，暴力Borůvka仍然在\(n^2\log\)级别，因此需要一些有性质的图来优化算法（一般是快速找到最小边权）。

星际联邦

完全图上每个点有点权\(a_i\)，定义\((u,v)(u\lt v)\)的边权为\(a_v-a_u\)，求最小生成树。

在每一轮需要找到每个点向外到另一个联通块内的最小边。注意到当\(i\)固定时，最小边要么是前缀\([1, i)\)的最大值取到的，要么是\((i, n]\)内的后缀最小值取到的。我们只需要对每个前缀维护最大值，以及和最大值不在同一个联通块内的最大值，后缀同理，就可以快速求出该联通块向外的最小边。时间复杂度为\(O(n \log n)\)。

#include<bits/stdc++.h>
using namespace std;
// ...（代码详见原文）

CF888G Xor-MST

完全图上每个点有点权\(a_i\)，定义\((u,v)(u\neq v)\)的边权为\(a_u \operatorname{xor} a_v\)，求最小生成树。

考虑放到trie树上维护异或和最值。这里的代码量还行，找个时间码了。

图

给定两颗带权无向树\(T_1,T_2\)，定义\(dis_i(x,y)\)表示树\(T_i\)上\(x,y\)间的距离，现有一完全二分图，左部，右部分别有\(n\)个点，定义左部点\(i\)与右部点\(j\)之间的边权为\(\max\limits_{x=1}^n(dis_1(i,x)+dis_2(j,x))\)，求完全二分图最小生成树。

https://h.hszxoj.com/d/hztg/contest/6716222721518607d314c04f/file/graph.cpp