h2. Indicaţii de rezolvare

O scurtă lecţie de teorie găsiţi în cartea '"Introducere in algoritmi"':http://zhuzeyuan.hp.infoseek.co.jp/ita/chap23.htm, Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, în exerciţiul $23-2$.

Toate informaţiile necesare le găsiţi în cartea '"Introducere in algoritmi"':http://zhuzeyuan.hp.infoseek.co.jp/ita/chap23.htm, Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest. În exerciţiul $23-2$ se tratează teoretic problema determinării componentelor biconexe.
 
Pentru a descompune graful în componente biconexe am folosit proprietăţile parcurgerii $DFS$. După o parcurgere $DFS$ muchiile grafului se vor clasifica în două categorii:
 
* muchii care aparţin arborelui $DFS$;
* muchii care nu aparţin arborelui şi care unesc un nod cu un strămoş al său, aceste muchii numindu-se muchii de întoarecere.
 
Problema determinării punctelor de articulaţie este strâns legată de problema determinării componentelor biconexe. După parcurgerea anterioară, un nod $X$ va fi nod de articulaţie dacă există cel puţin un fiu al său $Y$ din care nu se poate ajunge la un strămoş al lui $X$ pe un alt drum „în jos” în arborele $DFS$ şi apoi pe o muchie de întoarcere. Folosind o stivă în care reţinem muchiile din graf în ordinea în care sunt întâlnite în timpul parcurgerii, atunci când întâlnim un nod $X$ care are un fiu $Y$ cu proprietăţile de mai înainte, vom elimina din stivă toate muchiile, inclusiv muchia $(X, Y)$. Acest muchii formează o componentă biconexă.
 
Dacă graful este reprezentat prin liste de adiacenţă atunci complexitatea 'soluţiei':job_detail/236379?action=view-source este $O(N + M)$.

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