How to solve the following graph game

Consider the following game on an undirected graph G. There are two players, a red color player R and a blue color player B. Initially all edges of G are uncolored. The two players alternately c开发者_如何学Goolor an uncolored edge of G with their color until all edges are colored. The goal of B is that in the end, the blue-colored edges form a connected spanning subgraph of G. A connected spanning subgraph of G is a connected subgraph that contains all the vertexes of graph G. The goal of R is to prevent B from achieving his goal.

Assume that R starts the game. Suppose that both players play in the smartest way. Your task is to find out whether B will win the game.

Input: Each test case begins with a line of two integers n ( 1 <= n <= 10) and m (0 <= m <= 30), indicating the number of vertexes and edges in the graph. All vertexes are numbered from 0 to n-1. Then m lines follow. Each line contains two integers p and q ( 0 <= p, q < n) , indicating there is an edge between vertex p and vertex q.

Output: For each test case print a line which is either "YES" or "NO" indicating B will win the game or not.

Example:

3 4

0 1

1 2

2 0

0 2

Output: Yes

My idea: If we can find two disjoint spanning trees of the graph, then player B wins the game. Otherwise, A wins. 'Two disjoint spanning trees' means the edge sets of the two trees are disjoint

I wonder if you can prove or disprove my idea

Your idea is correct. Find a proof here: http://www.cadmo.ethz.ch/education/lectures/FS08/graph_algo/solution01.pdf

If you search for "connectivity game" or "maker breaker games" you should find some more interesting problems and algorithms.

So I think R should follow the following strategy:

Find the node with least degree (uncolored edges) (which does not have any Blue colored Edge)
call it N
if degree of N (uncolored edges) is 1 then R wins, bye bye
Find its adjacent nodes {N1,...,Nk}
Pick up M from {N1,...,Nk} such that degree (uncolored) of M (and M does not have any blue colored edge) is the least among the set
Color the edge Connecting from M to N
Repeat this.