浅谈 Kosaraju 的一类运用

本文参考 Kosaraju 魅力时刻 - Unyielding_Trilobite。

是的，这玩意是有用的。

我们现在要处理一个这样的问题：一张图，有 $n$ 个点，$m$ 组边，每组边形如 $(u,l,r)$，表示对于 $v\in[l,r]$，$u$ 有通向 $v$ 的边，有 $q$ 次询问，每次询问形如一个点是否能到达另外一个点。

我们当然可以线段树建图之后跑 Tarjan，但是常数太大了，有没有常数更小，甚至复杂度更好的做法呢？

有的有的。我们考虑直接大力 Kosaraju，那么问题变成了给你若干个区间 $[l_i,r_i]$，要你遍历这些区间，每个被区间覆盖到的点至少遍历一次。

直接遍历记录 vis 你肯定就直接 $O(n^2)$ 了，但是我们考虑并查集记录 vis，这就可以从一个点 $O(\alpha(n))$ 的查找到下一个没有遍历的点了？

事实上不加按秩合并也是对的，证明见 OI-wiki，我怕不会。

那么我们就可以在 $O(n\alpha(n))$ 之内解决这个问题了。

例题，二分一下建立 2-SAT 就变成上面的问题了。

例题二维版本，这道题我会在下篇文章讲，因为有一些问题没有解决。