Boruvka小鸡

我知道 $MST$ 的三种求法！

补题时遇到的船新科技！

考虑平时我们求 $MST$ 的两种做法，一种 $kruskl$ 是基于贪心每次加入一条最小边，而 $prim$ 则是把一个生成树向外扩展。

那结合这两种思想我们可以得到 $Boruvka$ 算法：

• 初始每个点独立为点集
• 每个点集尝试寻找向其他点集连边中权最小的一条，合并这两个点集
• 重复这个过程，直到只剩一个点集。

容易发现，这样操作的正确性显然，然后每次点集数量会起码缩水一半，故复杂度为 $O(T\log N)$ 其中 $T$ 我们查找最小权边的复杂度。

对于稠密图，边数接近 $n^2$ ，这个算法就不能朴素做，此时我们就要想办法优化查找最小权的边，可以使用各种 DS 来优化。

如 CF888G ，是一张完全图求异或 MST，看到异或最小值，我们有两种思路，要么上 trie ，要么上线性基，这里直接上 trie 就可以优化寻找最小边的复杂度至 $\log \texttt{值域}$ 级别。

同样，这一算法思想也可以用于在边数很大难以直接处理的时候计算联通块个数，如 $\texttt{ZROI2095}$。