AVA12:
Блин, FasterHarder, да прочитай ты уже написанное!

Тут очевидно, что если из некоторой вершины есть ребро, ведущее в зеленую, то сама эта вершина должна быть красной, и никакие подходы, никакие кривые пути этот факт не изменят. Вершина, покрашенная в красный, красной и останется.

Тут очевидно, что прежде чем покрасить вершину в зеленый, нужно покрасить все смежные с ней, а тогда ее цвет определяется однозначно и не меняется. Вершина, покрашенная в зеленый, зеленой и останется.

Здесь выбор порядка обхода вершин ни на что не влияет. Можно обходить вершины в случайном порядке - если применять только эти два правила, результат в любом случае будет один и тот же! Ты же перемудрил и взял откуда-то совершенно левый навороченный алгоритм, который не равнозначен этим двум простым правилам.


Можно лучше: берем все покрашенные вершины (изначально - все тупики) и строим циклический список всех непокрашенных вершин, ведущих к ним. И уже по этому общему списку гуляем.

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