图论 最小生成树 Boruvka算法

一、前导 1.Kruskal和Prim的回顾

首先我们对 K r u s k a l Kruskal Kruskal和 P r i m Prim Primu算法进行回顾：

• K r u s k a l Kruskal Kruskal算法的基本思想是维护一个森林，查询两个结点是否在同一棵树中，并连接两棵树。在实际的算法过程中，我们需要对边集进行排序，复杂度 O ( m log ⁡ m ) O(m \log m) O(mlogm)，并使用 O ( m log ⁡ n ) O(m \log n) O(mlogn)并查集维护集合。总复杂度 O ( m log ⁡ m ) O(m \log m) O(mlogm)。因此对于稠密图， K r u s k a l Kruskal Kruskal显得有些"水土不服"。
• P r i m Prim Prim算法的基本思想是每次需要寻找距离最小的一个结点(与Dijkstra’s Algorithm相似)，以及新的边来更新其它结点的距离。在寻找距离最小点的过程中，可以暴力查找，也可以采用堆维护进行优化。在使用二叉堆优化的加持下，复杂度 O ( ( n + m ) log ⁡ n ) O((n + m)\log n) O((n+m)logn)。相比于 K r u s k a l Kruskal Kruskal， P r i m Prim Prim更适用于稠密图。

对于最小生成树，我们一般将这类问题进行分类，对于稀松图选择 K r u s k a l Kruskal Kruskal求解，对于稠密图则使用 P r i m Prim Prim算法进行求解。

2.Boruvka算法引入

很容易发现，对于某些毒瘤的问题，边的数量极其大，而边集内部又存在各种规律可能需要套上各种数据结构加以优化。但是此时 K r u s k a l Kruskal Kruskal和 P r i m Prim Prim并不能很好的嵌合进这些数据结构。此时我们可以引入 B o r u v k a Boruvka Boruvka算法。

对于 B o r u v k a Boruvka Boruvka算法，一个比较笼统的表述是，一个多路增广版本的 K r u s k a l Kruskal Kruskal。它的思想是一开始所有点看做独立子集，每次遍历边找到两个集合(连通块)之间连接的最短边，不断扩大集合(连通块)直到所有点合并为一个集合(连通块)。

二、Brouvka原理与实现 1.基本原理

在并查集算法中，初始状态下我们将每个点视为一个独立的点集，并不断地合并集合。在 B r o u v k a Brouvka Brouvka算法中，我们在一开始将所有点视为独立子集，每次我们找到两个集合(即为连通块)之间的最短边，然后扩展连通块进行合并。

可以发现， B o r u v k a Boruvka Boruvka算法将求解最小生成树的问题分解为求连通块间最小边的问题。它的基本思想是：

生成树中所有顶点必然是连通的，所以两个不相交集必须连接起来才能构成生成树，而且所选择的连接边的权重必须最小，才能得到最小生成树。

2.基本过程

1. 首先将所有点视为各自独立的集合，初始化一个空的 M S T MST MST;
2. 当子集个数大于 1 1 1的时候，对各个子集和执行以下操作：
   1. 找到与当前集合有边的集合，选出权值最小的边；
   2. 如果该权值最小的边不在 M S T MST MST中；

3.实现

#include 
using namespace std;

const int N = 1e5 + 10;
const int M = 1e6 + 10;

struct node { int u, v, w; } edge[M];

int f[N], best[N];
bool vis[N];
int n, m;

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

inline const bool cmp(int u, int v){
    if(v == 0) return 1;
    if(edge[u].w != edge[v].w) return edge[u].w  n >> m;
    for(int i = 1; i > edge[i].u >> edge[i].v >> edge[i].w;
    for(int i = 1; i