When the graph has cycles, some positions might lead to draws. A draw happens when both players can force the game to repeat indefinitely. You need three states now: winning, losing, and drawing. A position is drawing if you can move to a drawing position but cannot move to a losing position.
The algorithm is more complex. You need to detect cycles and classify positions carefully. Fixed-point iteration works: keep updating position states until they stabilize.