~~时间复杂度只有O(AC)和O(TLE)~~
by Samuel_YHL @ 2020-08-12 11:30:08
我只知道tarjan缩点是O（n）的
by lndjy @ 2020-08-12 11:34:58
@[kuoluo03](/user/250699) 对于每一个点跑SPFA？那应该是 $O(n^2m)$ 的。
by Smile_Cindy @ 2020-08-12 11:35:06
如果只跑一遍，那就是 $O(nm)$ 的。
by Smile_Cindy @ 2020-08-12 11:35:37
$O(n^2k)$，$k$ 是一个点平均的入队次数，一般为 $2$，最大为 $m$
by _Album_ @ 2020-08-12 11:47:48
@[Alpha](/user/87058) tarjan缩点的时间复杂度不算进去吗
by mot1ve @ 2020-08-12 15:55:04
@[kuoluo03](/user/250699) $O(n+m)$ 在 $O(nm)$ 面前不需要考虑。
by Smile_Cindy @ 2020-08-12 16:00:50