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

Se dă un 'graf neorientat':http://mathworld.wolfram.com/UndirectedGraph.html $G = (V, E)$. Un graf se numeşte 'graf biconex':http://en.wikipedia.org/wiki/Biconnected_graph dacă nu are 'puncte de articulaţie':http://en.wikipedia.org/wiki/Articulation_vertex. O componentă biconexă a unui graf este un 'subgraf':http://en.wikipedia.org/wiki/Glossary_of_graph_theory#Subgraphs biconex maximal cu această proprietate.

Se dă un 'graf neorientat':http://mathworld.wolfram.com/UndirectedGraph.html $G = (V, E)$. Un graf se numeşte 'graf biconex':http://en.wikipedia.org/wiki/Biconnected_graph dacă nu are puncte de articulaţie. Un nod se numeşte punct de articulaţie dacă 'subgraful':http://en.wikipedia.org/wiki/Glossary_of_graph_theory#Subgraphs obţinut prin eliminarea nodului şi a muchiilor incidente cu acesta nu mai este conex. O componentă biconexă a unui graf este un subgraf biconex maximal cu această proprietate.

h2. Cerinţă

* 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 până la muchia $(X, Y)$ inclusiv. Acest muchii formează o componentă biconexă.

Problema determinării componentelor biconexe este strâns legată de problema determinării punctelor de articulaţie. 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 până la muchia $(X, Y)$ inclusiv. Acest muchii formează o componentă biconexă.

Dacă graful este reprezentat prin liste de adiacenţă atunci complexitatea 'algoritmului':job_detail/236392?action=view-source este $O(N + M)$.