算法简介：乌眼

Boruvka 算法是一个不常用的计算最小生成树的算法，通过不断地合并一个一个的连通块使用贪心的思想在 log 的复杂度求出结果。

算法演示：鸦羽

我们首先想到，对于点 u 和 v ，如果 v 是点 u 所有边中距离最短的点，那么这条边一定在最小生成树中。

那么不难做出第一步：把最短的边连起来，这样子就会把他们变成很多个连通块。这样的连通块最多有 n 个。

接下来，我们把每一个连通块都看成一个点，那么继续找出最短的那条边一直重复，这样的当我们把所有的连通块都变成一个连通块的时候，就得到了最优解。

每一次至少变成原来的二分之一，复杂度就是 $O(n+\cfrac n 2 + \cfrac n 4 + …)$ 也就是 $O(m\log n)$ 其中 m 是边的数量

这道题目的话，是一个完全图，完全图的特点就在于边特别多，像 kruskal 算法这种按照边作为复杂度的东西，显而易见就是会超时的，所以说这是候我们的 boruvka 就上场了。我们发现这种位运算的操作可以通过一些数据结构维护，但是这样的操作过程似乎不可以用 kruskal 做。

现在我们考虑如何去做这个操作使其可以用 Boruvka 算法做。我们发现异或这种相同为 0 不同为 1 的特性，使得高位具有决定性的操作。也就是说，我们可以用 trie 解决。

查看相关标签喵！