<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>

struct State {
  int C;
  int M;
  int T; // turn = 1 -> Mouse
};
class Solution {
public:
    int catMouseGame(vector<vector<int>>& graph) {
      int N = graph.size() - 1;
      vector <State> adj[51][51][2];
      int deg[51][51][2] = {0};
      int O[51][51][2];
      bool vis[51][51][2] = {0};
      memset(O, -1, sizeof(O));
      for (int C = 1; C <= N; C++) {
        for (int M = 0; M <= N; M++) {
          for (int T = 0; T < 2; T++) {
            int &o = O[C][M][T];
            if (C == M) {
              if (T == 0) o = 1;
              else o = 0;
            }
            if (M == 0) {
              if (T == 0) o = 0;
              else o = 1;
            }
            if (o == 0 || o == 1) 
              continue;
            State Cur = State(C, M, T);
            int F = (T == 0 ? C : M);
            for (int X : graph[F]) {
              int NC = (T == 0 ? X : C);
              int NM = (T == 1 ? X : M);
              if (NC != 0) {
                adj[NC][NM][!T].push_back(Cur);
                deg[C][M][T]++;
              }
            }
          }
        }
      }

      auto DFS = [&] (auto&DFS, int C, int M, int T) -> void {
        vis[C][M][T] = 1;
        for (State st : adj[C][M][T]) {
          if (!vis[st.C][st.M][st.T]) {
            if (O[C][M][T] == 0) {
              O[st.C][st.M][st.T] = 1;
            }
            else if (--deg[st.C][st.M][st.T] == 0) {
              O[st.C][st.M][st.T] = 0;
            }
            else continue;
            DFS(DFS, st.C, st.M, st.T);
          }
        }
      };

      for (int C = 1; C <= N; C++) {
        for (int M = 0; M <= N; M++) {
          for (int T = 0; T < 2; T++) {
            if (O[C][M][T] != -1 && !vis[C][M][T]) {
              DFS(DFS, C, M, T);
            }
          }
        }
      }
      if (O[2][1][1] == 1) return 1;
      else if (O[2][1][1] == 0) return 2;
      return 0;
    }
};
109925