自动搬运

查看原文

来自洛谷，原作者为

	dehsirehC 一个人的命运啊，

搬运于2025-08-24 23:04:01，当前版本为作者最后更新于2024-09-06 18:25:01，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

前言

部分分有点少，但出题人已经尽力了......

$30\%$ 的数据

对于每一个点， BFS 一遍找到所有它能到达的点，再暴力枚举每一个点判断是否合法。

总时间复杂度 $O(nm)$ 。

$60\%$ 的数据

考虑使用 bitset 优化 30% 的数据 中的算法，即用 bitset 表示一个点能到达的点的集合。

具体的，由于同一个强连通分量内的点互相可达，故可以先对图进行 缩点 变成一张有向无环图。

此时我们按照拓扑序从大到小计算每个点能到达的点，每次将它连出去的点的 bitset 或起来即可。

总时间复杂度 $O(\frac{nm}{\omega})$ ，其中 $\omega$ 大概可以看作 $64$ ，空间大约是 $n^2$ 个 bit 。

$100\%$ 的数据

同样的，先对图进行 缩点 变成一张有向无环图。当然不 缩点 也可以得到足足 $50\%$ 的分数！

注意到拓扑序比较大的点一定无法到达比较小的点，换句话说一个点只可能到达比它拓扑序大的点。

考虑对于每一个点算出它是否能到达所有拓扑序比它大的点，以及能否被所有拓扑序比它小的点到达。

接下来考虑如何计算前者，后者同理。按拓扑序从大到小不断加点，考虑一个点合法的充要条件。

若当前图有至少两个点入度为 $0$ ，则新加入的点不符合条件，因为它无法到达另一个入度为 $0$ 的点。

否则必定符合要求，考虑每个点只保留一个入边，最终每个点沿着入边走必定能走到当前新加入的点。

在 拓扑排序 的时候动态维护一下有多少个点入度为 $0$ 即可。总时间复杂度 $O(n+m)$ 。