<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 {
    int color[50][50][3];
    
public:
    int catMouseGame(vector<vector<int>>& graph) 
    {
        int N = graph.size();        
        queue<vector<int>>q;
        for (int i=0; i<N; i++)
            for (int turn=1; turn<=2; turn++)
            {
                color[0][i][turn] = 1;  // mouse win conditions
                q.push({0,i,turn});
                
                if (i!=0)               
                {
                    color[i][i][turn] = 2;  // cat win conditions
                    q.push({i,i,turn});
                }
            }
        
        while (!q.empty())
        {            
            int m = q.front()[0]; 
            int c = q.front()[1];
            int t = q.front()[2];            
            int status = color[m][c][t];
            q.pop();
                        
            for (auto nextNode: findAllParents(graph,m,c,t))
            {
                int m2 = nextNode[0];
                int c2 = nextNode[1];
                int t2 = nextNode[2];
                
                if (color[m2][c2][t2]!=0) continue; // has been determined
                
                if (t2==status)   // immediate win, (m2,c2,t2)->(m,c,t)
                {
                    color[m2][c2][t2] = status;
                    q.push({m2,c2,t2});                    
                }
                else if (allChildrenWin(graph, m2,c2,t2))    // eventually lose
                {
                    color[m2][c2][t2] = (t2==1)? 2:1;
                    q.push({m2,c2,t2});                
                }                
            }
        }
        return color[1][2][1];
    }
    
    
    vector<vector<int>> findAllParents(vector<vector<int>>& graph, int m, int c, int t)
    {
        vector<vector<int>>neighbours;
        if (t==1)
        {
            for (int c_next: graph[c])
                if (c_next!=0) neighbours.push_back({m,c_next,2});
        }
        else
        {
            for (int m_next: graph[m])
                neighbours.push_back({m_next,c,1});
        }
        return neighbours;
    }
    
    bool allChildrenWin(vector<vector<int>>& graph, int m, int c, int t)
    {
        if (t==1)
        {
            for (int m_next: graph[m])
                if (color[m_next][c][2]!=2)
                    return false;
        }
        else if (t==2)
        {
            for (int c_next: graph[c])
                if (c_next!=0 && color[m][c_next][1]!=1)
                    return false;
        }
        return true;
    }
};
172175