Repetytorium - Ćwiczenia 9
Poprzednie
Następne
Temat: Sortowanie topologiczne.
Sortowanie topologiczne
W teorii grafów sortowanie topologiczne
skierowanego grafu acyklicznego to liniowe uporządkowanie wierzchołków,
w którym jeśli istnieje krawędź skierowana prowadząca od wierzchołka x
do y, to x znajdzie się przed wierzchołkiem y. Innymi słowy, każdy
wierzchołek poprzedza wszystkie te wierzchołki, do których prowadzą
wychodzące od niego krawędzie.
Wierzchołki w każdym grafie acyklicznym skierowanym można posortować
topologicznie na jeden lub więcej sposobów.
Więcej informacji pod adresem
http://pl.wikipedia.org/wiki/Sortowanie_topologiczne
Zadanie
Na podstawie wiadomości o sortowaniu topologicznym rozwiąż zadanie 1022 na timusie.
Do rozwiązania zadania użyj algorytmu sortowania topologicznego przy użyciu przeszukiwania wgłąb DFS.