<p>A game on an <strong>undirected</strong> graph is played by two players, Mouse and Cat, who alternate turns.</p>

<p>The graph is given as follows: <code>graph[a]</code> is a list of all nodes <code>b</code> such that <code>ab</code> is an edge of the graph.</p>

<p>The mouse starts at node <code>1</code> and goes first, the cat starts at node <code>2</code> and goes second, and there is a hole at node <code>0</code>.</p>

<p>During each player&#39;s turn, they <strong>must</strong> travel along one&nbsp;edge of the graph that meets where they are.&nbsp; For example, if the Mouse is at node 1, it <strong>must</strong> travel to any node in <code>graph[1]</code>.</p>

<p>Additionally, it is not allowed for the Cat to travel to the Hole (node <code>0</code>).</p>

<p>Then, the game can end in three&nbsp;ways:</p>

<ul>
	<li>If ever the Cat occupies the same node as the Mouse, the Cat wins.</li>
	<li>If ever the Mouse reaches the Hole, the Mouse wins.</li>
	<li>If ever a position is repeated (i.e., the players are in the same position as a previous turn, and&nbsp;it is the same player&#39;s turn to move), the game is a draw.</li>
</ul>

<p>Given a <code>graph</code>, and assuming both players play optimally, return</p>

<ul>
	<li><code>1</code>&nbsp;if the mouse wins the game,</li>
	<li><code>2</code>&nbsp;if the cat wins the game, or</li>
	<li><code>0</code>&nbsp;if the game is a draw.</li>
</ul>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2020/11/17/cat1.jpg" style="width: 300px; height: 300px;" />
<pre>
<strong>Input:</strong> graph = [[2,5],[3],[0,4,5],[1,4,5],[2,3],[0,2,3]]
<strong>Output:</strong> 0
</pre>

<p><strong class="example">Example 2:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2020/11/17/cat2.jpg" style="width: 200px; height: 200px;" />
<pre>
<strong>Input:</strong> graph = [[1,3],[0],[3],[0,2]]
<strong>Output:</strong> 1
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>3 &lt;= graph.length &lt;= 50</code></li>
	<li><code>1&nbsp;&lt;= graph[i].length &lt; graph.length</code></li>
	<li><code>0 &lt;= graph[i][j] &lt; graph.length</code></li>
	<li><code>graph[i][j] != i</code></li>
	<li><code>graph[i]</code> is unique.</li>
	<li>The mouse and the cat can always move.&nbsp;</li>
</ul>

class Solution {
public:
    int catMouseGame(vector<vector<int>>& graph) {
        // this is a games in graph kinda problem
        // we can solve this problem using BFS/DFS on the state space
        // we have to do reverse BFS/DFS from the states for which we know the answer already

        // turn
        const int CAT_TURN = 2;
        const int MOUSE_TURN = 1;
        
        // colors (or) the result of a state
        const int DRAW = 0;
        const int CAT = 2;
        const int MOUSE = 1;

        int n = graph.size();

        // the color or the result of a state (or node in the state space)
        int color[n][n][3];
        // all the states initially have the color DRAW
        memset(color, DRAW, sizeof color);

        // the states for which we already know the result
        vector<vector<int>> final_states;

        // find the states for which we already know the answer
        for(int i=1; i<n; i++) {
            for(int turn : {CAT_TURN, MOUSE_TURN}) {
                final_states.push_back({0, i, turn});
                color[0][i][turn] = MOUSE;

                final_states.push_back({i, i, turn});
                color[i][i][turn] = CAT;
            }
        }

        // find the degree of each state
        int degree[n][n][3];
        memset(degree, 0, sizeof degree);

        for(int i=0; i<n; i++) {
            for(int j=1; j<n; j++) {
                degree[i][j][MOUSE_TURN] = graph[i].size();
                degree[i][j][CAT_TURN] = graph[j].size() - (find(graph[j].begin(), graph[j].end(), 0) != graph[j].end());
            }
        }

        // function for finding the parent states of a given state
        function<vector<vector<int>>(vector<int>&)> parent_states = [&](vector<int>& state) {
            int i=state[0], j=state[1], t=state[2];
            vector<vector<int>> states;

            if(t == MOUSE_TURN) {
                for(int k : graph[j]) {
                    if(k != 0)
                        states.push_back({i, k, CAT_TURN});
                }
            }
            else {
                for(int k : graph[i]) {
                    states.push_back({k, j, MOUSE_TURN});
                }
            }

            return states;
        };

        // function for doing reverse DFS from the given state
        function<void(vector<int>&)> solve = [&](vector<int>& curr_state) {
            int i=curr_state[0], j=curr_state[1], t=curr_state[2];
            int c = color[i][j][t];

            // go through the parent states of the current state
            for(vector<int>& parent_state : parent_states(curr_state)) {
                int ip=parent_state[0], jp=parent_state[1], tp=parent_state[2];
                int cp = color[ip][jp][tp];

                // if the parent node hasn't been colored yet (or the result is still undefined, i.e DRAW)
                if(cp == DRAW) {
                    // if parent state's turn is same as color of current state
                    if(tp == c) {
                        color[ip][jp][tp] = c;
                        // do reverse from this node now
                        solve(parent_state);
                    }
                    else {
                        // decrement the degree of the parent state
                        degree[ip][jp][tp]--;

                        if(degree[ip][jp][tp] == 0) {
                            // color the parent node with same color as current state
                            // as there in no way for the current node to win
                            color[ip][jp][tp] = c;
                            // do reverse DFS from the parent node now
                            solve(parent_state);
                        }
                    }
                }
            }
        }; 

        for(vector<int>& state : final_states) {
            solve(state);
        }

        return color[1][2][MOUSE_TURN];
    }
};
147275