Fişierul intrare/ieşire:	sortaret.in, sortaret.out	Sursă	ad-hoc
Autor	Arhiva Educationala	Adăugată de	Tabara Mihai •Tabara
Timp execuţie pe test	0.125 sec	Limită de memorie	20480 kbytes
Scorul tău	N/A	Dificultate	N/A

Poti vedea testele pentru aceasta problema accesand atasamentele.

Vezi solutiile trimise | Statistici

Sortare topologica

O sortare topologica a varfurilor unui graf orientat aciclic este o operatie de ordonare liniara a varfurilor, astfel incat, daca exista un arc ( i, j ), atunci i apare inaintea lui j in aceasta ordonare.

Date de intrare

In fisierul de intrare sortaret.in vom avea pe prima linie doua numere intregi N si M. Pe fiecare dintre urmatoarele M linii se vor afla cate doua numere intregi, separate intre ele printr-un spatiu, X si Y, cu semnificatia ca exista arc de la nodul X catre nodul Y.

Date de iesire

Fisierul de iesire sortaret.out va contine pe o singura linie N numere separate intre ele prin spatii, care reprezinta sortarea topologica a nodurilor grafului dat.

Restrictii

• 1 ≤ N ≤ 5000
• 1 ≤ N ≤ 7000

Exemplu

Indicatii de rezolvare

• O scurta prezentare a acestui subiect gasiti aici
• Algoritmul de Sortare Topologica il gasiti foarte bine explicat si in cartea <i>Introducere in algoritmi</i>, Thomas Cormen, editura Agora, Cluj-Napoca.

• Ideea din spatele rezolvarii consta intr-o parcurgere in adancime pentru a calcula timpii de terminare pentru fiecare varf v. Pe masura ce fiecare varf este terminat, se insereaza varful in capul unei liste simplu inlantuite. Parcurgerea listei va constitui solutia.
  Acest algoritm are o complexitate de {O($NM)$} deoarece cautarea in adancime necesita un timp {O($MN)$} iar inserarea fiecaruia din cele |N| varfuri in capul liste simplu inlantuite necesita timp {O($1)$}.

Probleme Similare

Cum se trimit solutii?