Boruvka算法

· · 算法·理论

流程：多轮进行 首先对于每个连通块寻找权值最小的边使得一端点位于连通块内，另一端点位于连通块外。然后逐个连边（需要判断是否已经是同一连通块），直至形成一个连通块。 正确性显然（考虑若形成环，则边上权值相等，此时去掉哪条边均可）。 复杂度证明：由于每轮每个连通块至少会与一个其他连通块连边，所以最多 $\log n$ 轮后便会形成一个连通块。 例题：$CF1648E$ $Air Reform$ 。 我们考虑对于补图直接建最小生成树，考虑到最小生成树的不可替换性，所以路径即为树上路径(这阐述了 $max$ 最小和 $sum$ 最小的关联为 $\Delta$，这在重心中也出现过)。 考虑用 $Boruvka$ 实现，为了找到合适的路径我们使用 $Kruskal$ 重构树（合理性：若已经连边则不优，原来的路径一定边数更多且权值更低）。 考虑对于连通块内一个点 $x$ 怎么做，我们现在需要在重构树的祖先上权值最小的点满足：祖先上有不在该连通块上且与 $x$ 无直接相连的点。 考虑如何判定，考虑转化到 $dfs$ 序上的一段区间，则显然我们仅需维护离 $x$ **之前/之后**的最近的合法点，考虑 $lca$ 较深者即可。又可发现这样的点随着连通而逐渐变少，则可以指针维护。 然后就可以直接暴力维护同连通块段了。