关于本题 Tarjan 做法的时间复杂度

P4306 [JSOI2010] 连通数

Cu ball
by _Cheems @ 2023-10-09 15:58:53


本题的 Tarjan 缩点是 $O(n^2)$ 的,拓扑排序部分用 bitset 优化可以做到 $O(\frac{n^3}{w})$,$w$ 是计算机位长。
by 369Pai @ 2023-10-11 21:08:32


|