swf: Замечу только, что всех путей в ациклическом орграфе может быть экспоненциальное количество от числа вершин.
Будет ли работать раскраска, ещё не поняла. Щас подумаю :)

Добавлено 18.03.21, 20:32
С раскраской всё правильно.
Всегда ли мы можем раскрасить вершины? Когда мы не можем покрасить. Если из непокрашенной вершины v есть путь в непокрашенную вершину u. А из непокрашенной u есть путь в непокрашенную v. Чтобы покрасить вершину v, надо знать цвета всех следующих, то есть надо знать и цвет u. А чтобы узнать цвет u, нужно знать цвета всех следующих, в том числе и v.
Но в этом случае между u и v замыкается орцикл, которого быть не должно.

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