Гуляем по графу

Ориентированный граф ациклический, а значит, мы можем расположить вершины в таком порядке, чтобы ребро шло из вершины с меньшим номером в вершину с большим номером. Запустим процесс. Будем идти по вершинам, начиная с первой, и закидывать их в группу с минимальным номером, чтобы требуемые условия выполнялись. Пусть мы дошли до -й вершины и не смогли её добавить ни в одну из групп. Это значит, что в -й группе есть вершина с некоторым номером из которой идёт ребро в А почему не получилось поместить вершину в группу? Потому что в ней есть некоторая вершина из которой идёт ребро в Продолжая такие рассуждения для всех групп, получим путь длины которого по условию быть не должно, пришли к противоречию.