Graph Theory37 sections · 1633 units
Open in Course

Problem - Coin Game on DAG (Part 5)

(Finding winning moves)

Once you know which positions are winning, you can also find the winning move. At a winning position, move to any losing position.

If you need to count the number of winning moves, iterate through all edges and count how many lead to losing positions. For more complex queries, you can precompute additional information during the backward induction phase. This extends the basic algorithm to answer richer questions about the game without increasing the time complexity.