FasterHarder:
изначально так и было (в первых сообщениях), а потом уже по совету amk инвертировал, но это ведь НЕ принципиально с т.з. алгоритма

AVA12, выше ведь писал, что планирую запускать BFS от каждого тупика, а сам тупик закрашен "красным". Насчет правил, да, согласен, конечно, и они выработаны, но здесь все равно, что-то не всегда четко, т к к конкретной вершине можно подойти разными путями, при этом она может иметь разный цвет в зависимости от подхода.

Вообще, надо бы разобраться подетальнее с этой раскраской, конечно, чтобы снять любые сомнения.
Все тупики получены. Сразу их все безраздумья красим в красный цвет. Тут однозначно!
Перебираем в цикле все тупики. Берем i-й тупик и запускаем от него BFS. Не уверен, что бфс тут идеально подходит, но вроде должен подходить) (прим. дуги к этому моменту в орграфе инвертированы + также все вершины кроме тупиковых имеют "серый" цвет, якобы непосещенные). Т е все возможны 3 цвета: красный (ход туда ведет к победе), зеленый (ход туда приводит к победе противника), серый.

возможные случаи раскраски:
1. стоим на красной вершине и дуга к серой ---> красим серую в зеленый - тут вроде однозначно.
2. стоим на зеленой вершине и дуга к серой ---> красим серую в красный - тут вроде однозначно.
3. стоим на зеленой и дуга к зеленой. хм... Тут момент: а надо ли зеленую перекрашивать в красный? получается, что, НЕТ! сделав вершину-достижения красной будем обман игрока, он подумает, что надо в нее заходить, а соперник потом переведет его дальше в красную). Т е вариант "зеленая-зеленая" оставляем без изменений
4. стоим на красной и дуга к красной. хм... Тут момент: а надо ли красную перекрашивать в зеленую? получается, что, ДА! если оставить красной, то это будет обманкой для игрока, т к соперник его следующим ходом переведет в красную.
все, др.комбинаций здесь нет.

что-то мне подсказывает, что это НЕТОЧНЫЙ алгоритм раскраски, который не учитывают все возможные случаи. Как обычно с графами, все намного тоньше и умнее)
что не так с подалгоритмом раскраски??

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