h2. Indicaţii de rezolvare
O scurtă lecţie de teorie găsiţi 'aici':http://www.cs.berkeley.edu/~vazirani/s99cs170/notes/lec12.pdf precum şi în cartea '"Introducere in algoritmi"':http://zhuzeyuan.hp.infoseek.co.jp/ita/chap23.htm, Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest.
O 'soluţie':job_detail/230456?action=view-source în complexitate $O(N^3^)$ este transformarea matricei de adiacenţă într-o matrice a drumurilor cu ajutorul algoritmului lui 'Roy-Warshall':problema/royfloyd. Cu ajutorul ei se va construi un nou graf neorientat în care muchia $(x, y)$ semnifică faptul că în graful precedent vârfurile $x$ şi $y$ sunt accesibile unul din celălalt. Astfel, problema s-a redus la 'determinarea componentelor conexe':problema/dfs într-un graf neorientat. Acest algoritm ar trebui să obţină $30p$.
O 'soluţie':job_detail/230425?action=view-source în complexitate $O(N + M)$ în cazul mediu, dar $O(N^2^)$ în cazul defavorabil poarte numele de algoritmul $plus-minus$. Algoritmul presupune alegerea unui nod arbitrat, $n$, şi parcurgerea în adâncime a grafului din acest nod. Nodurile atinse vor fi marcate cu $plus$. Apoi, în graful transpus '$G^T^$':http://en.wikipedia.org/wiki/Transpose_graph, din acelaşi nod se va face o nouă parcurgere în adâncime, iar nodurile atinse acum vor fi marcate cu $minus$. Astfel, componenta tare conexă din care face parte nodul $n$ este formată din nodurile marcate cu $plus$ şi $minus$. Se elimină această componentă şi se reia algoritmul din alt nod. Explicaţia constă în faptul că în nodurile cu $plus$ se poate ajunge din $n$, iar din nodurile cu $minus$ se poate ajunge în $n$. Acest algoritm ar trebui să obţină $60p$.
Soluţia optimă, în complexitate $O(N + M)$, care foloseşte paradigma $plus-minus$, este {'algoritmul lui Kosaraju':http://en.wikipedia.org/wiki/Kosaraju's_algorithm}. Acestă 'soluţie':job_detail/230485?action=view-source obţine $90p - 100p$. {'Algoritmul lui Tarjan':http://en.wikipedia.org/wiki/Tarjan's_strongly_connected_components_algorithm} se comportă cel mai bine în practică. Soluţia se găseşte 'aici':job_detail/230484?action=view-source şi obţine $100p$.
O 'soluţie':job_detail/230456?action=view-source în complexitate $O(N^3^)$ este transformarea matricei de adiacenţă într-o matrice a drumurilor cu ajutorul algoritmului lui 'Roy-Warshall':problema/royfloyd. Astfel se va construi un nou graf neorientat în care muchia $(x, y)$ semnifică faptul că în graful precedent vârfurile $x$ şi $y$ sunt accesibile unul din celălalt. Astfel, problema s-a redus la 'determinarea componentelor conexe':problema/dfs într-un graf neorientat. Acest algoritm ar trebui să obţină $30$ de puncte.
O 'soluţie':job_detail/230425?action=view-source în complexitate $O(N + M)$ în cazul mediu, dar $O(N^2^)$ în cazul defavorabil poarte numele de algoritmul $plus-minus$. Algoritmul presupune alegerea unui nod arbitrat, $n$, şi parcurgerea în adâncime a grafului din acest nod. Nodurile atinse vor fi marcate cu $plus$. Apoi, în graful transpus '$G^T^$':http://en.wikipedia.org/wiki/Transpose_graph, din acelaşi nod se va face o nouă parcurgere în adâncime, iar nodurile atinse acum vor fi marcate cu $minus$. Astfel, componenta tare conexă din care face parte nodul $n$ este formată din nodurile marcate cu $plus$ şi $minus$. Se elimină această componentă şi se reia algoritmul din alt nod. Explicaţia constă în faptul că în nodurile cu $plus$ se poate ajunge din $n$, iar din nodurile cu $minus$ se poate ajunge în $n$. Acest algoritm ar trebui să obţină $60$ de puncte.
Soluţia optimă, în complexitate $O(N + M)$, care foloseşte paradigma $plus-minus$, este {'algoritmul lui Kosaraju':http://en.wikipedia.org/wiki/Kosaraju's_algorithm}. Acestă 'soluţie':job_detail/230485?action=view-source obţine $90 - 100$ de puncte. {'Algoritmul lui Tarjan':http://en.wikipedia.org/wiki/Tarjan's_strongly_connected_components_algorithm} se comportă cel mai bine în practică. Soluţia se găseşte 'aici':job_detail/230484?action=view-source şi obţine $100$ de puncte.
h2. Probleme suplimentare
În algoritmii care lucrează cu grafuri orientate este adeseori nevoie să se transforme graful orientat într-un 'graf orientat aciclic':http://en.wikipedia.org/wiki/Directed_acyclic_graph. Acest lucru se poate realiza cu algoritmul determinării componentelor tare conexe, care divizează problema în mai multe subprobleme, una pentru fiecare componentă tare conexă, deoarece graful subproblemelor, adică al componentelor, este aciclic. Soluţiile lor se vor combina urmând structura legăturilor dintre componente.
Printre problemele care folosesc ideile de mai sus se numără:
* 'Retele':problema/retele
* 'Proving Equivalences':http://2008.nwerc.eu/problems/nwerc08-problemset.pdf
* 'Proving Equivalences':http://2008.nwerc.eu/problems/nwerc08-problemset.pdf, _NWERC 2008_
* 'Plan':problema/plan
* 'Plimbare':problema/plimbare
* 'Synchrograph':http://acm.sgu.ru/problem.php?contest=0&problem=219
* 'Synchrograph':http://acm.sgu.ru/problem.php?contest=0&problem=219, _SGU_
* 'Obiective':problema/obiective
* {'Aplicaţii la $2-SAT$':2-sat#aplicatii}
* 'Dep':problema/dep, _ONI 2008, Baraj_
* {'Aplicaţii ale $2-SAT$':2-sat#aplicatii}
== include(page="template/taskfooter" task_id="ctc") ==
