Problem statement

A mouse and a cat play a game on an undirected graph given as an adjacency list: graph[a] lists every node b joined to a.

The mouse starts at node 1 and moves first; the cat starts at node 2; node 0 is the hole. On each turn the player to move must travel along one edge from its current node. The cat may never enter the hole.

The game ends when:

• the cat reaches the mouse's node — the cat wins;
• the mouse reaches the hole — the mouse wins;
• a position (both nodes and whose turn it is) repeats — the game is a draw.

Assuming both play optimally, return 1 if the mouse wins, 2 if the cat wins, or 0 for a draw.

Example 1

Input: graph = [[2,5],[3],[0,4,5],[1,4,5],[2,3],[0,2,3]]
Output: 0

Example 2

Input: graph = [[1,3],[0],[3],[0,2]]
Output: 1
Explanation: The mouse steps straight from node 1 into the hole.

Example 3

Input: graph = [[2],[2],[0,1]]
Output: 2
Explanation: The mouse's only move is onto the cat's node 2.

Constraints

• 3 <= graph.length <= 50
• 1 <= graph[i].length < graph.length
• 0 <= graph[i][j] < graph.length
• graph[i][j] != i
• graph[i] has no duplicates
• b is in graph[a] exactly when a is in graph[b]
• the cat and the mouse can always move

Hints for Cat and Mouse

1. Hint 1

   A game state is (mouse node, cat node, whose turn) — at most 2 · n^2 of them. The outcome of the game is a function of the state.

2. Hint 2

   Some states are decided outright: mouse in the hole (mouse wins) and mouse and cat on the same node (cat wins). Propagate backwards from them.

3. Hint 3

   A state is a win for the player to move if some move reaches a state they win; it is a loss if all moves reach states the opponent wins. Track how many undecided moves each state has left; whatever is never decided is a draw.

How to solve Cat and Mouse

Plain DFS with memoisation gets draws wrong, because a state's value can depend on states still on the stack. Retrograde analysis avoids that: start from the decided terminal states and work backwards, the way endgame tables are built.

Approach

1. Colour every state (m, c, turn) as undecided. Count, for each state, how many moves the player to move has (degree); the cat never counts the hole.
2. Mark terminal states and push them on a queue: (0, c, *) mouse wins, (c, c, *) cat wins, for every c >= 1.
3. Pop a decided state. For each undecided parent (a state one move earlier, by the other player): if the parent's mover wins in the popped state, the parent is a win for that mover; otherwise decrement the parent's degree, and when it hits zero every move loses, so the parent is a loss for its mover. Push newly decided parents.
4. Return the colour of (1, 2, mouse to move); undecided means draw (0).

Why it works

Each step decides a state only from facts already proven: one winning move suffices, and a loss needs every move to be proven losing. Any state that can be forced to a terminal outcome in finitely many moves is eventually reached by this propagation. A state never decided has, for its mover, at least one move that avoids a forced loss forever — with optimal play the game repeats a position, which is a draw.

Complexity

• Time — O(n^3)
• Space — O(n^2)

Pitfalls

• Do not let the cat move into node 0 — not when generating parents, and not when counting its degree.
• Terminal states have no outgoing moves to count; never decrement their degree.
• A top-down DFS that treats "currently on the stack" as a draw is wrong on some graphs; use the queue-based propagation.

Reference solution

Python

from collections import deque
from typing import List

def catMouseGame(graph: List[List[int]]) -> int:
    n = len(graph)
    MOUSE, CAT = 1, 2
    color = [[[0, 0] for _ in range(n)] for _ in range(n)]
    degree = [[[len(graph[m]), len(graph[c]) - (0 in graph[c])] for c in range(n)] for m in range(n)]
    q = deque()
    for c in range(1, n):
        for t in range(2):
            color[0][c][t] = MOUSE
            q.append((0, c, t))
            color[c][c][t] = CAT
            q.append((c, c, t))
    while q:
        m, c, t = q.popleft()
        res = color[m][c][t]
        if t == 1:
            # the mouse moved into this state: parents have the mouse to move
            for pm in graph[m]:
                if color[pm][c][0]:
                    continue
                if res == MOUSE:
                    color[pm][c][0] = MOUSE
                    q.append((pm, c, 0))
                else:
                    degree[pm][c][0] -= 1
                    if degree[pm][c][0] == 0:
                        color[pm][c][0] = CAT
                        q.append((pm, c, 0))
        else:
            for pc in graph[c]:
                if pc == 0 or color[m][pc][1]:
                    continue
                if res == CAT:
                    color[m][pc][1] = CAT
                    q.append((m, pc, 1))
                else:
                    degree[m][pc][1] -= 1
                    if degree[m][pc][1] == 0:
                        color[m][pc][1] = MOUSE
                        q.append((m, pc, 1))
    return color[1][2][0]

Java

public static int catMouseGame(int[][] graph) {
    int n = graph.length;
    int[] color = new int[n * n * 2], degree = new int[n * n * 2];
    for (int m = 0; m < n; m++)
        for (int c = 0; c < n; c++) {
            int catDeg = graph[c].length;
            for (int v : graph[c]) if (v == 0) catDeg--;
            degree[(m * n + c) * 2] = graph[m].length;
            degree[(m * n + c) * 2 + 1] = catDeg;
        }
    int[] q = new int[n * n * 2];
    int head = 0, tail = 0;
    for (int c = 1; c < n; c++)
        for (int t = 0; t < 2; t++) {
            color[(c) * 2 + t] = 1; q[tail++] = c * 2 + t;
            color[(c * n + c) * 2 + t] = 2; q[tail++] = (c * n + c) * 2 + t;
        }
    while (head < tail) {
        int s = q[head++], t = s % 2, m = s / 2 / n, c = s / 2 % n, res = color[s];
        if (t == 1) {
            for (int pm : graph[m]) {
                int p = (pm * n + c) * 2;
                if (color[p] != 0) continue;
                if (res == 1 || --degree[p] == 0) { color[p] = res == 1 ? 1 : 2; q[tail++] = p; }
            }
        } else {
            for (int pc : graph[c]) {
                if (pc == 0) continue;
                int p = (m * n + pc) * 2 + 1;
                if (color[p] != 0) continue;
                if (res == 2 || --degree[p] == 0) { color[p] = res == 2 ? 2 : 1; q[tail++] = p; }
            }
        }
    }
    return color[(1 * n + 2) * 2];
}

C++

int catMouseGame(vector<vector<int>>& graph) {
    int n = graph.size();
    vector<int> color(n * n * 2, 0), degree(n * n * 2, 0), q;
    for (int m = 0; m < n; m++)
        for (int c = 0; c < n; c++) {
            int catDeg = graph[c].size();
            for (int v : graph[c]) if (v == 0) catDeg--;
            degree[(m * n + c) * 2] = graph[m].size();
            degree[(m * n + c) * 2 + 1] = catDeg;
        }
    for (int c = 1; c < n; c++)
        for (int t = 0; t < 2; t++) {
            color[c * 2 + t] = 1; q.push_back(c * 2 + t);
            color[(c * n + c) * 2 + t] = 2; q.push_back((c * n + c) * 2 + t);
        }
    for (size_t h = 0; h < q.size(); h++) {
        int s = q[h], t = s % 2, m = s / 2 / n, c = s / 2 % n, res = color[s];
        if (t == 1) {
            for (int pm : graph[m]) {
                int p = (pm * n + c) * 2;
                if (color[p]) continue;
                if (res == 1 || --degree[p] == 0) { color[p] = res == 1 ? 1 : 2; q.push_back(p); }
            }
        } else {
            for (int pc : graph[c]) {
                if (pc == 0) continue;
                int p = (m * n + pc) * 2 + 1;
                if (color[p]) continue;
                if (res == 2 || --degree[p] == 0) { color[p] = res == 2 ? 2 : 1; q.push_back(p); }
            }
        }
    }
    return color[(1 * n + 2) * 2];
}

JavaScript

var catMouseGame = function(graph) {
    var n = graph.length, MOUSE = 1, CAT = 2;
    var color = [], degree = [];
    var idx = function(m, c, t) { return (m * n + c) * 2 + t; };
    for (var m = 0; m < n; m++) {
        for (var c = 0; c < n; c++) {
            var catDeg = graph[c].length - (graph[c].indexOf(0) >= 0 ? 1 : 0);
            color.push(0, 0);
            degree.push(graph[m].length, catDeg);
        }
    }
    var q = [];
    for (var k = 1; k < n; k++) {
        for (var t = 0; t < 2; t++) {
            color[idx(0, k, t)] = MOUSE; q.push([0, k, t]);
            color[idx(k, k, t)] = CAT; q.push([k, k, t]);
        }
    }
    for (var h = 0; h < q.length; h++) {
        var cm = q[h][0], cc = q[h][1], ct = q[h][2], res = color[idx(cm, cc, ct)];
        if (ct === 1) {
            for (var a = 0; a < graph[cm].length; a++) {
                var p = idx(graph[cm][a], cc, 0);
                if (color[p]) continue;
                if (res === MOUSE || --degree[p] === 0) { color[p] = res === MOUSE ? MOUSE : CAT; q.push([graph[cm][a], cc, 0]); }
            }
        } else {
            for (var b = 0; b < graph[cc].length; b++) {
                var pc = graph[cc][b];
                if (pc === 0) continue;
                var p2 = idx(cm, pc, 1);
                if (color[p2]) continue;
                if (res === CAT || --degree[p2] === 0) { color[p2] = res === CAT ? CAT : MOUSE; q.push([cm, pc, 1]); }
            }
        }
    }
    return color[idx(1, 2, 0)];
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More dynamic programming problems

• Rank Transform of a Matrix Hard
• Shortest Distance After Road Addition Queries II Hard
• Time Taken to Mark All Nodes Hard
• Number of Possible Sets of Closing Branches Hard
• Count Visited Nodes in a Directed Graph Hard
• Minimum Edge Reversals So Every Node Is Reachable Hard