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':job_detail/230434?action=view-source optimă, în complexitate $O(N + M)$, care foloseşte paradigma $plus-minus$, este {'algoritmul lui Kosaraju':http://en.wikipedia.org/wiki/Kosaraju's_algorithm}. {'Algoritmul lui Tarjan':http://en.wikipedia.org/wiki/Tarjan's_strongly_connected_components_algorithm} se comportă cel mai bine în practică.

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':http://infoarena.ro/job_detail/230484?action=view-source.

h2. Probleme suplimentare