Sortare Topologica

sortaret

| 1 2 3 4 6 7 8 5 9
|

h2. Indicatii de rezolvare

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 idee de rezolvare este sa introducem, pe rand, intr-o lista, nodurile care la un moment dat un gradul exterior zero. Odata ce un nod este introdus in lista, vom scoate nodul respectiv din graf si vom considera in continuare graful ramas. O implementare directa are complexitatea $O(N^2^)$ si se gaseste 'aici':job_detail/144431?action=view-source. Daca rafinam aceasta idee, introducand succesiv nodurile intr-o coada, putem obtine complexitatea $O(N+M)$, sursa se gaseste 'aici':job_detail/144253?action=view-source.
* O alta posibila idee de rezolvare consta intr-o parcurgere in adancime pentru a calcula timpii de terminare pentru fiecare varf $v$. Pe masura ce fiecare varf este terminat, este inserat 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(N+M)$ iar inserarea fiecaruia din cele {$|N|$} varfuri in capul liste simplu inlantuite necesita timp $O(1)$. Sursa se gaseste 'aici':http://infoarena.ro/job_detail/144206?action=view-source.
h2. Probleme similare

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

* "Topological Sort":http://www.algorithmist.com/index.php/UVa_10305
* "Spreadsheet":http://www.algorithmist.com/index.php/UVa_196

h3. Alte probleme
 
"Topological Sort":http://www.algorithmist.com/index.php/UVa_10305
"Honest":http://campion.edu.ro/problems/3/237/honest_ro.htm
"Spreadsheet":http://www.algorithmist.com/index.php/UVa_196
"Obiective":http://infoarena.ro/problema/obiective

== include(page="template/taskfooter" task_id="sortaret") ==