PROBLEM LINK:
Author: Sai Sandeep
Tester: Aditya Shah
DIFFICULTY:
MEDIUM-HARD
PREREQUISITES:
PROBLEM:
Two players play a game on graph. First player picks a node. Second player picks a node which is not selected already and is adjacent to the previous node. And so on. The player to pick the last node wins.
Given the description of Graph, Determine which player will win.
QUICK EXPLANATION:
Player 2 wins iff there is a Perfect Matching in the Graph.
EXPLANATION:
Suppose the graph has perfect matching. Then Player 2 will simply choose the matched vertex for every vertex Player 1 chooses. Thus, Player 1 will lose out on vertices first.
Now, what happens if there is no perfect matching in the graph ?
Assume the graph does not have perfect matching. Select any maximum matching in the graph. Player 1 picks a vertex which is not there in the maximum matching. Such a vertex exists.(why ?)
Now, whenever Player 2 selects a vertex x, Player 1 chooses the vertex which is matched to vertex x in the maximum matching. Why is it that x is matched to some vertex in the maximum matching ? Suppose x is not matched to any vertex. Then, we have obtained an alternating augmenting path from the vertex that we started to x. But, a maximum matching cannot have alternating augmenting path.
Now, Player 2 will run out of vertices first.
See this for basic explanation about Augmenting paths.
To check if a graph has a perfect matching or not, we can use blossom shrinking algorithm. Please refer to Author’s solution for the implementation.
AUTHOR’S SOLUTION:
Author’s solution can be found here.