h3. Indicatii de rezolvare

O scurta prezentare a acestui subiect gasiti "aici":http://en.wikipedia.org/wiki/Topological_sorting
Algoritmul de Sortare Topologica il gasiti foarte bine explicat si in cartea <i>Introducere in algoritmi</i>, Thomas Cormen, editura Agora, Cluj-Napoca.

* O scurta prezentare a acestui subiect gasiti "aici":http://en.wikipedia.org/wiki/Topological_sorting
* 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(N+M) deoarece cautarea in adancime necesita un timp O(M+N) iar inserarea fiecaruia din cele |N| varfuri in capul liste simplu inlantuite necesita timp O(1).

* 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($N$+$M$)$} deoarece cautarea in adancime necesita un timp {$O($M$+$N$)$} iar inserarea fiecaruia din cele {$|N|$} varfuri in capul liste simplu inlantuite necesita timp {$O($1$)$}.

h3. Probleme Similare