Game King

dehsirehC · 2024-09-06 18:25:01 · 题解

前言

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

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

总时间复杂度 O(nm) 。

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

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

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

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

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

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

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

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

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

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

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