Cat and Mouse - Implementation

States: $O(n^2 \cdot 2)$ for $n$ nodes. Each state has an outcome: MOUSE_WIN, CAT_WIN, or UNKNOWN. Base cases: mouse at 0 = MOUSE_WIN. Mouse and cat at same node = CAT_WIN. Work backwards: if all of cat's moves lead to MOUSE_WIN, then cat loses. If any of mouse's moves leads to MOUSE_WIN, mouse wins. Remaining UNKNOWN states after propagation = DRAW. Both players can force a cycle. Time: $O(n^2 \cdot moves)$, Space: $O(n^2)$ for storing state outcomes.

Time complexity: $O(n^3)$.

Space complexity: $O(n^2)$.