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 |
Explicaţie
...
