h2. Date de intrare

Fişierul de intrare $ctc.in$ conţine pe prima linie două numere naturale $N$, $M$ ce reprezintă numărul de noduri din $G$ şi numărul muchiilor. Pe următoarele $M$ linii se vor afla câte două numere naturale $x$ şi $y$, separate prin spaţiu, reprezentând muchia orientată $(x, y)$.

Fişierul de intrare $ctc.in$ conţine pe prima linie două numere naturale $N$ si $M$ ce reprezintă numărul de noduri din $G$ şi numărul muchiilor. Pe următoarele $M$ linii se vor afla câte două numere naturale $x$ şi $y$, separate prin spaţiu, reprezentând muchia orientată $(x, y)$.

h2. Date de ieşire

În fişierul de ieşire $ctc.out$ veţi afişa pe prima linie un singur număr reprezentând numărul componentelor tare conexe. Pe fiecare din următoarele linii se va scrie câte o componentă tare conexă prin enumerarea nodurilor componente. Ordinea lor poate fi oricum.

În fişierul de ieşire $ctc.out$ se va afişa pe prima linie un singur număr reprezentând numărul componentelor tare conexe. Pe fiecare din următoarele linii se va scrie câte o componentă tare conexă prin enumerarea nodurilor componente. Acestea pot fi afişate în orice ordine.

h2. Restricţii
* $1 ≤ N ≤ 100 000$
* $1 ≤ M ≤ 200 000$

* Pentru $30%$ din teste: $1 ≤ N ≤ 100$, $1 ≤ M ≤ 500$
* Pentru $60%$ din teste: $1 ≤ N ≤ 5 000$, $1 ≤ M ≤ 25 000$
* Pentru aflarea corectă a numărului componentelor tare conexe se va acorda $40%$ din punctaj şi încă $60%$ pentru enumerarea corectă a lor.

* Pentru $30%$ din teste, $1 ≤ N ≤ 100$ si $1 ≤ M ≤ 500$
* Pentru $60%$ din teste, $1 ≤ N ≤ 5 000$ si $1 ≤ M ≤ 25 000$
* Pentru aflarea corectă doar a numărului componentelor tare conexe se va acorda $40%$ din punctaj

h2. Exemplu

4 5 6 7 8
|

h3. Explicaţie

!> problema/ctc?Ctc.png 60%!

!problema/ctc?Ctc.png!

h3. Explicaţie

În graful orientat din exemplu componentele tare conexe sunt reprezentate cu nuanţe diferite de gri. Aici, $1$ $2$ $3$ reprezintă prima componentă tare conexă, iar $4$ $5$ $6$ $7$ $8$ cea de a doua.

În graful orientat din exemplu componentele tare conexe sunt reprezentate cu nuanţe diferite de gri. Aici, {$1$ $2$ $3$} reprezintă prima componentă tare conexă, iar {$4$ $5$ $6$ $7$ $8$} cea de a doua.

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

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, _NWERC 2008_
* 'Plan':problema/plan

* 'Plimbare':problema/plimbare

* {'2-SAT, Soluţia $O(M + N)$':2-sat#solutie4}
* 'Proving Equivalences':http://2008.nwerc.eu/problems/nwerc08-problemset.pdf
* '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
* 'Dep':problema/dep, _ONI 2008, Baraj_
* {'Aplicaţii ale $2-SAT$':2-sat#aplicatii}

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

3511