Revizia anterioară Revizia următoare
| Fişierul intrare/ieşire: | biconex.in, biconex.out | Sursă | Arhiva educationala |
| Autor | Arhiva Educationala | Adăugată de |  Marius Stroe •Marius |
| Timp execuţie pe test | 0.2 sec | Limită de memorie | 524288 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Poti vedea testele pentru aceasta problema accesand atasamentele.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 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.in | biconex.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
O scurtă lecţie de teorie găsiţi în cartea "Introducere in algoritmi", Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, în exerciţiul 23-2.
