Szkic:

Wstępne przetwarzanie: liczymy domknięcie przechodnie wejściowego grafu G, odwracamy
w nim kierunki wszystkich krawędzi i otrzymany graf (oznaczmy go G') zapamiętujemy
jako listę zbiorów incydencji.

Algorytm: rozbijamy naszą zmianę porządku topologicznego na złożenie inwersji, czyli
zamian miejscami dwóch elementów porządku. Intuicyjnie, jeśli zmiana była niewielka,
to i inwersji będzie mało. Teraz dla każdej inwersji elementu i-tego z j-tym, i < j,
rozważamy zbiór wierzchołków {a_{i+1}, a_{i+2}, ..., a_{j-1}} i liczymy jego
teoriomnogościowe przecięcie ze zbiorem krawędzi wychodzącym w G' z wierzchołka a_j.
Jeśli któreś przecięcie wyjdzie niepuste, to psuje ono porządek topologiczny, w
przeciwnym wypadku otrzymana permutacja dalej jest porządkiem.

Wydaje mi się, że to działa, choć mogłem coś pochrzanić. Sprawdzenie poprawności i
szczegóły implementacyjne takie jak wybór reprezentacji zbiorów pozostawiam jako
ćwiczenie.

--D.