# Borůvka 算法

1. 计算每个点分别属于哪个连通块。将每个连通块都设为“没有最小边”。
2. 遍历每条边 $(u, v)$ ，如果 $u$ 和 $v$ 不在同一个连通块，就用这条边的边权分别更新 $u$ 和 $v$ 所在连通块的最小边。
3. 如果所有连通块都没有最小边，退出程序，此时的 $E’$ 就是原图最小生成森林的边集。否则，将每个有最小边的连通块的最小边加入 $E’$ ，返回第一步。

$$\begin{array}{ll} 1 & \textbf{Input. } \text{A graph }G\text{ whose edges have distinct weights. } \ 2 & \textbf{Output. } \text{The minimum spanning forest of }G . \ 3 & \textbf{Method. } \ 4 & \text{Initialize a forest }F\text{ to be a set of one-vertex trees} \ 5 & \textbf{while } \text{True} \ 6 & \qquad \text{Find the components of }F\text{ and label each vertex of }G\text{ by its component } \ 7 & \qquad \text{Initialize the cheapest edge for each component to “None”} \ 8 & \qquad \textbf{for } \text{each edge }(u, v)\text{ of }G \ 9 & \qquad\qquad \textbf{if } u\text{ and }v\text{ have different component labels} \ 10 & \qquad\qquad\qquad \textbf{if } (u, v)\text{ is cheaper than the cheapest edge for the component of }u \ 11 & \qquad\qquad\qquad\qquad\text{ Set }(u, v)\text{ as the cheapest edge for the component of }u \ 12 & \qquad\qquad\qquad \textbf{if } (u, v)\text{ is cheaper than the cheapest edge for the component of }v \ 13 & \qquad\qquad\qquad\qquad\text{ Set }(u, v)\text{ as the cheapest edge for the component of }v \ 14 & \qquad \textbf{if }\text{ all components’cheapest edges are “None”} \ 15 & \qquad\qquad \textbf{return } F \ 16 & \qquad \textbf{for }\text{ each component whose cheapest edge is not “None”} \ 17 & \qquad\qquad\text{ Add its cheapest edge to }F \ \end{array}$$

# Xor-MST

P.S. 直接按照上述流程实现 Borůvka 算法会超时