Однажды у нас на тренировке была такая задача: дан ориентированный граф без циклов, задается множество ребер, у которых нужно поменять направление. Известно, что если у всех этих ребер поменять направление, то сохранится ацикличность. Нужно так выбрать порядок изменения направлений, чтобы ни на каком шаге не появился цикл. Вершин до 1000, ребер до 10000.
Буду признателен тому, кто подскажет идею решения. Сам пока додумался только до того, что на каждом шаге имеет смысл менять направление только у того ребра, у которого нужно его поменять в итоге.
Comments (0)
