AVA12: FasterHarder, нету тут никаких тонкостей. Просто не надо слишком мудрить, надо тупо следовать правилам: если из непокрашенной вершины можно попасть в зеленую (ход в которую гарантирует победу), то красим текущую вершину в красный цвет (ход сюда ведет к поражению), если из непокрашенной вершины все ребра ведут в красные, то красим текущую вершину в зеленый. В цикле гуляем по всем непокрашенным вершинам графа и применяем эти два правила (если возможно) до тех пор, пока все вершины не будут покрашены.

P. S. У тебя на картинке цвета инвертированы. По-моему нагляднее так: красный цвет - "ты туда не ходи", зеленый цвет - "ты сюда ходи".

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