在无向图G上考虑以下游戏.有两个玩家,红色玩家R和蓝色玩家B.最初G的所有边缘都是未着色的.两个玩家交替地将G的未着色边缘与其颜色着色,直到所有边缘都被着色.B的目标是最终,蓝色边缘形成G的连接跨越子图.G的连接跨越子图是包含图G的所有顶点的连通子图.R的目标是防止B从实现他的目标.
假设R开始游戏.假设两个玩家都以最聪明的方式玩游戏.你的任务是找出B是否会赢得比赛.
输入:每个测试用例以两个整数n(1 <= n <= 10)和m(0 <= m <= 30)的行开始,表示图中顶点和边的数量.所有顶点的编号均为0到n-1.然后m行跟随.每行包含两个整数p和q(0 <= p,q <n),表示在顶点p和顶点q之间存在边.
输出:对于每个测试用例,打印一条"是"或"否"的线,表示B将赢得比赛.
例:
3 4
0 1
1 2
2 0
0 2
输出:是的
我的想法:如果我们能找到图中两个不相交的生成树,则玩家B赢得游戏.否则,A获胜."两个不相交的生长树"意味着两棵树的边缘集是不相交的
我想知道你是否可以证明或反驳我的想法
是否有任何适用的方法来找到无向图的两个不相交的生成树或检查某个图是否有两个不相交的生成树
给定无向图和连通图G，找到直径最小的生成树。