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_, Thomas Cormen, editura Agora, Cluj-Napoca.

O soluţie în complexitate $O(N^3^)$ este transformarea matricei de adiacenţă într-o matrice a drumurilor cu ajutoul 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.
O soluţie î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$. 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$.

O soluţie în complexitate $O(N^3^)$ este transformarea matricei de adiacenţă într-o matrice a drumurilor cu ajutoul 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 î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)$, 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ă şi nu este cu nimic mai greu de înţeles decât celelalte.

h2. Probleme suplimentare