Last Updated: 13 Feb, 2021

Tom and Jerry

Hard

Asked in company

Solve now

Problem statement

Tom and Jerry are playing a game. In this game, they are given an undirected graph of ‘N’ vertices labelled from 0 to 'N' - 1 and ‘M’ edges. They will take alternate turns starting with Jerry.

At the beginning, Jerry is at node 1, Tom is at node 2 and there is a hole at node 0. In each turn, a player can move to any other node which has a direct edge with the node in which they are currently present, with a condition that Tom cannot move to node 0.

Now the game can end in three ways :

1) If ever Tom occupies the same node as Jerry, Tom wins.

2) If ever Jerry reaches the Hole, Jerry wins.

3) If ever a position is repeated, the game is a draw.

Your task is to find who wins the game or is there a draw between the two if both the players play optimally.

Example:

Example

In the above graph, Tom has only one choice to go to node 3. Jerry also has only one option to go to node 0. And the first turn will be taken by Jerry so it will go to node 0 and hence win the game. So we will return 1.

Input format:

The first line of input contains an integer ‘T’ denoting the number of test cases.

The first line of each test case contains two space-separated integers ‘N’ and ‘M’ denoting the number of vertices and the number of edges in the undirected graph.

The next ‘M’ lines each contain two space-separated integers ‘u’ and ‘v’, denoting an edge from vertex ‘u’ to vertex ‘v’.

Output format:

For each test case, return 0 if the game draws, 1 if Jerry wins the game, or 2 if Tom wins the game.

Output for each test case should be in a separate line.

Note:

You don't need to print anything, it has already been taken care of. Just implement the given function.

Constraints:

1 <= T <= 10
1 <= N <= 50
1 <= M <= 300
1 <= u, v <= N

Time Limit: 1 sec

Solve now

Approaches

01 Approach

The basic idea is to do a memory cache search. Here we have 3 dimensions: At time T, the position of Jerry X, and position of Tom Y, so at any time and any position F(T, X, Y) should have a value, either 0 or 1 or 2.

Here 0 means draw, 1 means Jerry wins, and 2 means Tom wins.

Actually here we are doing colouring of the graph so if it’s Jerry’s turn and any of the child of the current node is 1 we will set current node’s value as 1 which means Jerry can come to this current node without being caught by Tom, but if the value of all children is 2 then the value of current node will also be 2 which implies Tom will catch Jerry at this node in any case. We can also understand this intuition by taking the current turn as Tom’s turn in the same way.

We will take a 3D array ‘DP[T][X][Y]' initialized to -1.
Tom and Jerry will never revisit the visited nodes because if they visit, it will result in a draw so the length of a maximum path by anyone will be of size ‘N’. So making a total of 2 * ‘N’ steps or maximum value of ‘T’ will be 2 * ‘N'.
So we know the maximum value of ‘T’ can be 2 * ‘N’ and maximum value of ‘X’ and ‘Y’ can be 'N'. Now the total states of ‘F’ can be 2 * ‘N’ * ‘N’ * ‘N’ = 2 * ‘N’ ^ 3.
There are ‘N’ nodes, so after 2 * ‘N’ steps, if we still can't decide who wins, the chase game will continue forever and return 0.
So we have a total of 2 * 'N'* ‘N’ * ‘N’ = 2 * ‘N’ ^ 3 status.
There is some position for whom we already know who will win:
- F(*, 0,*) = 1, when Jerry go-to position, Jerry wins.
- F(*, Y, Y) = 2, when Jerry and Tom get to the same position, then Tom wins.
- F(2 * 'N',*,*) return 0, because, after this, it will repeat forever.
So there can be two cases :
If the current turn is of Jerry then, first of all, we will check above three conditions if none of getting satisfied then do:
- Check the value of ‘DP[T][X][Y]’:
  - If ‘DP[T][X][Y]’ is not equal to -1 then we know we have already calculated the result for the current state so return ‘DP[T][X][Y]’.
  - Else do:
    - Increase ‘T’ by 1 and check the status of all children of the current node which we can also say neighbours of Jerry.
    - If the status of any neighbour is 1 then set 'DP[T][X][Y]'=1 and return 1.
    - If the status of all neighbours is 2 then ‘DP[T][X][Y]’=2 and return 2.
    - Else ‘DP[T][X][Y]’=0 and return 0.
We can similarly process for Tom’s turn with just two changes :
- Increase ‘T’ by 1 and check the status of all children of the current node which we can also say neighbour of Tom.
- If the status of any neighbour is 2 then set ‘DP[T][X][Y]’=2 and return 2.
- If the status of all neighbours is 1 then ‘DP[T][X][Y]’=1 and return 1.

Solve now