Atenţie! Aceasta este o versiune veche a paginii, scrisă la 2008-12-27 10:38:38.
Revizia anterioară   Revizia următoare  

 

Fişierul intrare/ieşire:biconex.in, biconex.outSursăArhiva educationala
AutorArhiva EducationalaAdăugată deMariusMarius Stroe Marius
Timp execuţie pe test0.4 secLimită de memorie524288 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Componente biconexe

Se dă un graf neorientat G = (V, E). Un graf se numeşte graf biconex dacă nu are puncte de articulaţie. O componentă biconexă a unui graf este un subgraf biconex maximal cu această proprietate.

Cerinţă

Dându-se un graf neorientat G = (V, E) se cere să se determine componentele sale biconexe.

Date de intrare

Fişierul de intrare biconex.in conţine pe prima linie două numere naturale N şi 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 neorientată (x, y).

Date de ieşire

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

Restricţii

  • 2 ≤ N ≤ 100 000
  • 1 ≤ M ≤ 200 000
  • Pentru aflarea corectă doar a numărului componentelor biconexe se va acorda 40% din punctaj.

Exemplu

biconex.inbiconex.out
8 9
1 2
2 3
3 4
4 1
1 5
5 6
6 7
7 5
7 8
4
1 2 3 4
7 8
5 6 7
1 5

Explicaţie

În graful neorientat din exemplu componentele sale biconexe sunt reprezentate prin cerculeţe. Notaţi că o muchie poate aparţine unei singure componente biconexe pe când un nod poate aparţine mai multor componente biconexe.

Indicaţii de rezolvare

Toate informaţiile necesare le găsiţi în cartea "Introducere in algoritmi", 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 este O(N + M).

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?