Akina: Начинать надо с "построения всех путей в графе". В данном случае строятся все пути от исходной вершины, приводящие в тупик. Далее - ищем "нечётные пути" (пути с нечётным числом рёбер), от которых "чётные" ответвляются только на "нечётных" шагах, а также "чётные" с ветвлением на "чётных" шагах, имеющих ответвление на "нечётный" путь на "нечётном" шаге, и т.п.

Реально это решается обратной задачей - т.е. после построения всех путей начинаем "закрашивать" проигрышные пути, сначала от тупиков, потом на "чётных" ветвлениях. Если в итоге получился незакрашенный путь от исходной вершины - первый выиграл, иначе выиграл второй (само собой предполагаем, что игроки делают наилучшие ходы).

https://forum.sources.ru/index.php?showtopic=421261&view=findpost&p=3845436