浅谈 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 就变成上面的问题了。

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