缩点拓排吧
by fast_photon @ 2023-08-01 14:48:20
@[fast_photon](/user/539724) 这个不是 $O(nm)$ 的吗
by __ex @ 2023-08-01 14:54:45
@[__ex](/user/389425)
缩点是 n+m 的啊
by fast_photon @ 2023-08-01 15:09:55
@[fast_photon](/user/539724) 确实啊，拓扑排序不是 $nm$ 吗
by __ex @ 2023-08-01 15:15:24
@[__ex](/user/389425)
拓扑排序凭什么是 O(nm)，每个点最多被拓排一次，每条边最多被删除一次
by fast_photon @ 2023-08-01 15:17:16
还要更新它的状态，要乘个 $n$ 吧
by __ex @ 2023-08-01 15:17:30
@[fast_photon](/user/539724) 使用 ``bitset`` 转移的时间是 $\frac{n}{w}$。
by lsj2009 @ 2023-08-01 15:17:46
本身是 n+m 吧
by __ex @ 2023-08-01 15:17:57
Floyed
by Jerry_heng @ 2024-02-21 21:03:55