Boruvka & Kosaraju

它们都是图论中的冷门算法，且能用来解决一部分困难的问题。

Kosaraju

先说这个，这个比较简单。

简单来说就是两遍 dfs 即可求出强连通分量，利用了后序 dfn 的某些性质。

流程：

dfs 一遍，回溯的时候记录 dfn。
在反图上由 dfn 从大到小每次从没搜过的点遍历一遍，并把遍历到的点都加入同一个强连通分量，编号是拓扑序反序。

代码：

void d(int x) {vis[x]=1;for(int v:G[x]) if(!vis[v]) d(v);dfx[++*dfx]=x;}
void d2(int x) {!col[x]&&(col[x]=++*col);for(int v:uG[x]) if(!col[v]) col[v]=col[x],d2(v);}
void scc() {
    F(i,1,n) if(!vis[i]) d(i);
    UF(i,n,1) if(!col[dfx[i]]) d2(dfx[i]);
}

它最大的优势就是好写，同时并不需要访问所有出边，仅需要遍历每个点即可。

于是我们就可以用经典查询后继利器 bitset 来完成后继的查询，达成 $\Theta(\frac{n^2}\omega)$ 的优秀复杂度，这适用于动态加边动态缩点。

例题

区间求 scc， $n\le150,m\le3\times 10^5,q\le5\times 10^4$ 。

莫队 + $\text{Kosaraju}$ ，复杂度 $\Theta(q\frac{n^2}{\omega}+m\sqrt q)$ 。

类似的题求最小生成树和边双都是比较简单的，每个线段树节点都是 $\Theta(n)$ 的信息，也可以分块。

Boruvka

求最小生成树的。

流程：

初始把每个点视为一个连通块。
遍历连通块间的边，每次都更新每个连通块向外的最小边。
连上每个连通块向外的最小边，更新成新的连通块。

每走一遍流程连通块数量至少减半，复杂度 $\Theta(m\log n)$ 。

通常适用于 $n^2$ 条边但边是抽象定义的图求最小生成树。

依照问题的不同，我们绝大多数情况下可以直接将两个连通块的任意两点连一条边，这点可以保证原树不同但重构树相同。

请注意以上这句话是错的，仅 $\text{Kruskal}$ 算法有这样的性质，其他算法均不行。

例题 CF1550F Jumping Around

数轴上顺次有 $n$ 个点 $a_1 < a_2 < \cdots < a_n$ 。

有一只小青蛙，初始时在 $a_s$ 处。小青蛙有两个参数：步长 $d$ 和灵活程度 $k$ 。其中，步长 $d$ 是确定的，而灵活程度 $k$ 是可以调整的。

小青蛙可以从某个点跳到另一个点。但这是有要求的：小青蛙能从 $a_i$ 跳到 $a_j$ ，当且仅当 $d-k\leq |a_i-a_j|\leq d+k$ 。

给定 $a_1,...,a_n$ 和 $d$ 。你需要回答 $q$ 次询问，每次询问给定一个下标 $i$ 和灵活程度 $k$ ，你需要回答：此时的小青蛙能否跳到 $a_i$ ？

$1\leq n,q\leq 2\times 10^5$ ， $1\leq s,i\leq n$ ， $1\leq a_i,d,k\leq 10^6$ ， $a_1 < a_2 < \cdots < a_n$ 。

考虑连一张完全图，其中两个点间的边权是两个点能直接跳过去的最小 $k$ ，求出它的最小生成树，那我们的询问就相当于一个简单的路径最小值判断。

但我们连不出来完全图，只能想办法另辟蹊径。

$\text{Boruvka}$ 的优秀性质让我们可以每次不管怎么搞只要 $\Theta(ns)$ 能搞出最短边就行了，这个要求相当的宽松。

这是一条直线上，所以我们可以每次查一个连通块前删掉 std::set 中该连通块的点，查完了再加回来，复杂度 $\Theta(q+n\log^2 n)$ 。

代码。

沙东 2023 二轮省集 D4T1

一个完全图，有 $m$ 条边边权给定，剩下的边权都是 $|x-y|$ ，求 $\text{mst}$ 边权和。

$n\le 10^9,m\le 10^5,w\ge 0$ 。

考虑把这些点平铺在序列上，把没有特殊边的点称为平凡点。

我们可以看到那些相邻的平凡点一定会连上它们之间长为 $1$ 的边，且位于这个相邻块的中间的点一定不会向外连边（可以都挪到左边或右边，一定不劣），这样整个图的点数就缩到了 $\Theta(m)$ 级别。

（不要把每个相邻块看作一个整体，把两个边上的关键点分开考虑，这样就是对点集的操作，更为优美。）

现在就可以上 $\text{Boruvka}$ 了。

首先是特殊边，这个直接扫一遍更新即可。

然后非特殊边可以搞一个 set，每个块查的时候先把块内元素删除，每个点查的时候再把特殊边出点给删除， $\Theta(m\log^2 m)$ 。

然后你发现把上述过程换成链表就可以 $\Theta(m\log m)$ ，非常舒适。

CF888G Xor-MST

给定 $n$ 个点和点权，两个点之间的边权是 $a_i\oplus a_j$ ，求最小生成树边权和。

$n\le2\times 10^5$ 。

对每个连通块维护一个 $\text{Trie}$ ，每次把该 $\text{Trie}$ 里的点从全局 $\text{Trie}$ 里删掉然后查询即可。

当然有更简单的做法：将原序列排序，则等价于 $\text{Trie}$ 上有 $n-1$ 个点有两个儿子，在这些点上把左右儿子组成的连通块合并即可，显然左右儿子内部肯定优先联通才会启用当前点这个不优的边权，若 $<n-1$ 个点有两个儿子，则一定有两个相同的权值，此时不必在意。