P9220

· · 题解

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

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

缩点之后做一些讨论感觉很对，容易考虑一个平局情况为一个 \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)。挺妙的。