FasterHarder: В общем это задача, взята из раздела "Обход графа в глубину", т е она исключительно на DFS и никаких BFS даже юзать, вроде нельзя)
+ не нужно здесь заниматься полным перебором чего-либо, вроде как

А ведь все сходится относительно DFS:
1. на 1ом этапе определяем все тупики через DFS
2. на 2ом этапе также, юзая ДФС, можно пораскрашивать и получить ответ

т е кроме DFS ничего и не нужно)

кстати, ДФС ведь бывает разного вида: рекурсивная и через стек. ИМХО, через стек попроще, т к рекурсия сама по себе (по своей природе) обладает повышенной встроенной сложностью. Вроде как порядок обхода вершин орграфа через рекурсию или стек в ДФС одинаков. Вроде бы. В графах я ни в чем не уверен, все надо проверять по "тысячу" раз...
--------------------------
в общем всем спс, кто пытался помочь
пока буду думать, как произвести раскраску, юзая ДФС. Оч. сильно сомневаюсь, что приду к решению, но попробовать ведь надо))

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