这是本文档旧的修订版!
题目大意:给定一个无向图,初始时有一个token在s点,两个玩家Join Player和Cut Player轮流行动,CutPlayer先动。Cut Player每次可以移除一条和token所在位置相邻的边, Join Player每次可以将token沿着一条未删除边移动, 如果token在某刻被移动到t则Join Player获胜,否则Cut Player获胜,求双方最优策略下的胜者。
从 $t$ 考虑,能够走到 $t$ 的点与 $t$ 必有两条及以上的边相连,将这些点和 $t$ 加入集合,若其他点有两条及以上的边连向该集合,则再将这些点加入集合,最后若 $s$ 在集合中则 Join Player 胜利,否则 Cut Player 胜利。
时间复杂度 $O(n+m)$