== include(page="template/taskheader" task_id="ctc") ==

Se dă un graf orientat $G = (V, E)$. O componentă tare conexă a grafului orientat $G$ este o mulţime maximală de vârfuri $U$ inclusă în $V$, astfel încât, pentru fiecare pereche de vârfuri $u$ şi $v$ din $U$ avem atât drum de la $u$ la $v$ cât şi drum de la $v$ la $u$. Cu alte cuvinte, vâfurile $u$ şi $v$ sunt accesibile unul din celălalt.

Se dă un 'graf orientat':http://en.wikipedia.org/wiki/Directed_graph $G = (V, E)$. O 'componentă tare conexă':http://en.wikipedia.org/wiki/Strongly_connected_component a grafului orientat $G$ este o mulţime maximală de vârfuri $U$ inclusă în $V$, astfel încât, pentru fiecare pereche de vârfuri $u$ şi $v$ din $U$ avem atât drum de la $u$ la $v$ cât şi drum de la $v$ la $u$. Cu alte cuvinte, vâfurile $u$ şi $v$ sunt accesibile unul din celălalt.

h2. Cerinţă

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$.
 

h2. Probleme suplimentare
* 'Plimbare':problema/plimbare