FasterHarder: поломав голову, все-таки кое в чем прозрел!)
во-первых, я НЕ отказался от своих правил из сообщения №13, а переработал их
во-вторых, и самое главное, меня осенила великая мысль)) и я наконец-то таки понял, где был этот тонкий момент не понимания
На самом деле все оказалось еще тоньше и я не уверен, что это предел "тонкости" здесь...

самый-самый-пресамый важный момент, который не учитывал был в том, что ДФС надо было запускать ПОВТОРНО из вершин, которые уже раскрашены и меняют свой цвет на противоположный, т е НЕДОСТАТОЧНО сменить цвет и "забыть". Это тотально важный момент, который я НЕ учитывал вообще. Да, возможно, многие мне об этом писали здесь, но ведать я не понял их мысль.

Итак, свод правил раскраски. Предполагается, что дуги инвертированы + тупики найдены + покрашены в красный цвет. Задача любого игрока встать на красную вершину. Непосещенные вершины имеют белый цвет.
1. если вершина белая и в нее попадают из зеленой, то она становится красной.
2. если вершина белая и в нее попадают из красной, то она становится зеленой.
3. если вершина красная и в нее попадают из красной, то она становится зеленой! И этого НЕДОСТАТОЧНО! Теперь надо запускать ДФС из этой перекрашенной вершины (хотя раньше ДФС из этой вершины УЖЕ был запущен!!). По факту получается "вложенный" ДФС. Это тотально важно! И именно этот момент я раньше НЕ учитывал и получал лютейшие проблемы)
4. если вершина зеленая и в нее попадают из зеленой, то...оч.тоже интересный момент...
надо проверять всех ее соседей на исходном орграфе (без инвертирования дуг, который) и:
4.1. если все соседи имеют зеленый цвет (не уверен, но это вроде возможно, только при наличии единственного соседа, но не суть...), то красим в красный + запускаем от нее ДФС
4.2. если хотя бы один сосед имеет красный цвет, то оставляем зеленым (вот здесь есть частично отсылка к сообщению №16)
тут еще есть подвариант, когда несколько соседей ЕЩЕ НЕ раскрашены, а все раскрашенные соседи зеленые...хм...вроде (вроде!!) оставлять также надо зеленым. Позже, др.пути либо дадут красного соседа либо получим вариант №4.1 и она автоматически перекраситься в красный.

все! повторю: что самое важное, что я достиг в этом анализе по сравнению со своим старым - запуск ДФС от только что перекрашенной вершины.
-------------------------------------------------------------------------------------------------------------------------------------------
С уверенностью в 99% напишу, что ставлю под сомнение правильность алгоритмов раскраски, который претендуют раскрасить все вершины, посетив их по одному разу!! Если выше, кто-то приводил такой вариант, то с вероятностью 99% он не прав)) Это будет работать не на всех графах, а только на тривиальных.
-------------------------------------
А теперь покрасим граф, предложенный Akina в сообщении №10. кстати, спс ему за такую конфигурацию графа, т к в нем собраны очень проблемные моменты, которые не "видны" сходу.
____________.png (, : 37)
стартовая вершина №1. В процессе раскраски эта вершина ЧЕТЫРЕ РАЗА МЕНЯЛА СВОЙ ЦВЕТ!!!: красный (первый путь: 86421), зеленый (231), красный (87531) и наконец приняла свой окончательный вариант ЗЕЛЕНЫЙ (21).
---------------------------------------------------------------
Выводы:
1. невозможно раскрасить вершины, посетив их по одному разу
2. каждый новый путь (новых заход ДфС) уточняет выигрышную стратегию, перекрашивая вершины, полученные на предыдущих итерациях
-------------------------------------------------------------
Если кому не лень + он НЕ согласен с приведенным сводом правил (по сути, алгоритмом изложенными выше в этом посте), то просьба просто скинуть граф, который я НЕ смогу раскрасить правильно, посмотрим))

Является ли данный алгоритм оптимальным, с точки зрения производительности?? Далеко не уверен, но др.способа я не вижу. Вариант с четностью-нечетностью, предложенный Akina, возможно и оптимальнее, но он гораздо сложнее))) мне его не поднять 100%, поэтому даже не буду пытаться понять его)
-------------------------------------------
И последнее: если реализовать визуальную раскраску графа, то граф будет "мигать". Речь о сложных конфигурациях, с тысячами вершин и большим числом дуг. Каждый новый путь будет "уточнять" выигрышную стратегию и лишь на последнем пути она будет получена окончательно, т е когда будет рассмотрен ПОСЛЕДНИЙ тупик и его последний путь, ведущий к стартовой вершине. До этого момент победитель НЕ определен!!!

спс за внимание, я кончил)

Добавлено 20.03.21, 19:49
единственный, самый-самый единственный момент еще есть, который вроде понятен на 99%, но 100% уверенности нет: победная стратегия НА КАЖДОМ ХОДЕ содержит ход в красную вершину или нет...вроде, да! но чую, что подстава может быть, хотя на 99%, что да...

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