Determining the winner of a two-player game on a graph is PTIME-complete for explicit graphs. You can solve it in polynomial time using backward induction. For implicit graphs (where the graph is given by a succinct representing), the problem can be PSPACE-complete or even EXPTIME-complete.
In competitive programming, you always have explicit graphs with manageable sizes, so polynomial algorithms suffice.