You need three arrays: one for the outcome of each state, one for the degree of each state, and a queue for BFS. Initialize the queue with all terminal states.
Process states level by level, marking wins and losses as you go. The code structure is similar to topological sort with additional logic for tracking whose turn it is and checking win conditions. Time complexity is states times the average degree, giving in the worst case.