题意传送门 LeeCode 913 猫和老鼠题解任意图上博弈,可参考 Games on arbitrary graphs。对于此类博弈,胜负态与博弈者相关。简单而言,将博弈双方的状态转移 (i,u,v)(i,u,v)(i,u,v) 建反图,其中 iii 代表当前准备出手的一方,u,vu,vu,v 分别为博弈双方所在节点。在反图上没有入边的节点一定为某一方的获胜态;那么从这样的节点,按照一般胜负态转移的规则,对其前驱状态进行胜负态判断。最终,不能明确胜负态的状态为平局态。class Solutio