Graph Theory37 sections · 1633 units
Open in Course

Problem - Cat and Mouse (Part 5)

(Degree array technique)

The degree array stores how many unvisited children each state has. When you mark a state, decrement the degree of its parents. If a parent's degree reaches zero and it has not been marked as winning, it must be a loss.

All its moves lead to the opponent winning. This technique ensures you only mark states when you have complete information about all possible moves. Think of it like topological processing: states are resolved once all their successors have been classified.