Revizia anterioară Revizia următoare
| Fişierul intrare/ieşire: | ciclueuler.in, ciclueuler.out | Sursă | Arhiva educationala |
| Autor | Arhiva Educationala | Adăugată de |  Lucian Boca •amadaeus |
| Timp execuţie pe test | 0.4 sec | Limită de memorie | 65536 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Poti vedea testele pentru aceasta problema accesand atasamentele.Vezi solutiile trimise | Statistici
Ciclu Eulerian
Fie un multigraf G = (V,E). Un ciclu al lui G se numeste Eulerian daca viziteaza toate muchiile din E exact o singura data. G se numeste Eulerian daca admite un ciclu Eulerian.
Cerinta
Fiind dat un multigraf G = (V,E), determinati daca acesta este Eulerian. In caz afirmativ, gasiti un ciclu Eulerian al sau.
Date de intrare
Fisierul de intrare ciclueuler.in contine pe prima linie numerele N si M, reprezentand numarul nodurilor, respectiv numarul muchiilor din G. Pe urmatoarele M linii se afla cate o pereche de numere u v, decriind o muchie a multigrafului, cu extremitatile in nodurile u si v.
Date de iesire
In fisierul de iesire ciclueuler.out veti tipari M numere x1 x2 ... xM, cu proprietatea ca (x1,x2), (x2,x3), ..., (xM,x1) sunt muchiile ciclului Eulerian determinat, sau numarul -1, in cazul in care G nu este Eulerian.
Restrictii
- 1 ≤ N ≤ 100 000
- 1 ≤ M ≤ 500 000
- Solutia nu este unica; orice solutie valida va primi punctajul maxim.
Exemplu
| ciclueuler.in | ciclueuler.out |
|---|---|
| 4 6 1 2 1 3 2 2 2 3 3 4 3 4 | 1 2 2 3 4 3 |
Explicatie
Ciclul format din muchiile (1,2), (2,2), (2,3), (3,4), (4,3), (3,1), in aceasta ordine, este un ciclu Eulerian.
Solutie
Conform unei teoreme datorate lui Leonhard Euler, un multigraf este Eulerian (admite un ciclu Eulerian) daca si numai daca este conex si toate nodurile sale au grad par. Pentru a construi un astfel de ciclu putem folosi urmatoarele variante:
- Generam toate ciclurile simple ale multigrafului (spre exemplu, folosind metoda backtracking) si verificam proprietatea Euleriana. O astfel de abordare are, insa, complexitate exponentiala in raport cu dimensiunea datelor de intrare si o consideram lipsita de utilitate practica.
- Folosind algoritmul lui Fleury, pornim de la un nod oarecare si, la fiecare pas, parcurgem o muchie a carei stergere din graf nu l-ar deconecta. Stergem muchia respectiva si, deplasandu-ne in celalalt capat al ei, continuam algoritmul in aceeasi maniera pana cand vom epuiza toate muchiile grafului. Ciclul obtinut este Eulerian.
Pentru implementarea algoritmului lui Fleury, putem face o parcurgere in adancime din nodul de start, etichetand muchiile dupa tipul lor (muchii de arbore si muchii de intoarcere). La fiecare pas in construirea ciclului, vom alege intotdeauna muchiile de intoarcere inaintea muchiilor de arbore. Implementata cu grija, aceasta solutie are complexitate liniara.
[...]
