antros11
28-03-2015 16:27:55
Witam, ostatnio spotkałem się z problemem sortowanie topologicznego, którego nie potrafię rozwiązać. Otóż "treść" problemu brzmi mniej więcej tak:
Należy posortować podane na wejściu zadania w kolejności ich wykonywania.
W pierwszym wierszu wejścia podane są dwie liczby naturalne n ≤ 105 i m ≤ 105 oznaczające odpowiednio liczbę zadań do wykonania i liczbę warunków. W każdym z następnych m wierszy podane są dwie liczby naturalne ai, bi, informujące nas o tym, że zadanie ai musi zostać wykonane przed zadaniem bi. Każde zadanie ma unikalny identyfikator - liczbę naturalną z przedziału obustronnie domkniętego [1, n].
Twój program powinien wypisać zadania w kolejności ich wykonywania. Jeśli dwa zadania mogą być wykonane w tym samym momencie, najpierw należy wykonać zadania o większym numerze. Jeśli nie istnieje kolejność wykonywania zadań spełniająca wszystkie podane warunki, Twój program powinien wypisać słowo "NIE"
Jakieś pomysły/porady/programy?