自动搬运

查看原文

来自洛谷，原作者为

	nytyq .

搬运于2025-08-24 22:46:29，当前版本为作者最后更新于2025-08-18 21:49:26，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

似乎分类讨论，我真不懂博弈论。

能到达的点（包括自身）颜色翻转。

缩点之后做一些讨论感觉很对，容易考虑一个平局情况为一个 $\text{SCC}$ 内部颜色不统一，无论 Alice 还是 Bob 怎么变都不可能赢。

下文的图均为 DAG，即缩点之后。

Alice 必胜的情况：

假如图中只有一个黑点，Alice 直接染就赢了，还有一种情况就是，令当前拓扑序中第一个黑点为 $P$，那么接下来 $P$ 所领导的一颗子树都必须是完全黑的，而且所有的黑点都必须集中在这颗子树下，只有这样 Alice 翻转 $P$ 之后会赢。

Bob 必胜的情况

图中全白，则 Alice 一定染黑，Bob 只需染白就赢了。接入图中两个黑点，Alice 染其一，Bob 染其一，Bob 赢，注意图中的黑色需要孤立不然 Alice 直接赢。考虑只有两个点，黑点连向白点，Alice 如果染黑色点，那么局势变成白连黑，Bob 赢，同理，Alice 如果然白色点，Bob 赢。

综上。时间复杂度就是 tarjan 的 $\mathcal{O}(n+m)$。挺妙的。