题目链接：https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=3792

题目大意：给一张图，先手先选定两个不同的点 $A,B$ ，然后开始游戏，每轮先手指定一个未固定的边删掉，后手指定一个没被固定的边固定，如果 $A,B$ 最后联通，则后手获胜，否则先手获胜，问后手是否必胜。

做法

这道题目非常经典，又叫：Shannon’s Switching Game。

又有个变体问题：没有指定 $A,B$ 了，后手的目的是最后要是个联通图。

这两个问题的后手必胜的充要条件是：图中有两个交集为 $0$ 的生成树。

对于变体问题的充分性是比较好证明的，采用归纳+缩边的方法就行，详情请看：https://zhuanlan.zhihu.com/p/33862629 。

也可以用拟阵中的基进行证明，这里不再赘述。

但是必要性我不会证明，所以这道题目在此留一个坑，就此作罢。

坑

学会 Shannon’s Switching Game 。

知道这个判定条件后后面就好搞了，怎么判定呢？

要有个生成树，且在这个生成树外还有一个生成树，前者是图拟阵，后者是图拟阵的对偶拟阵，所以就是图拟阵与图拟阵的对偶拟阵的拟阵交。

时间复杂度：$O(Tm^3)$ 。

1
没有，不会证明，懒得写代码了。