Revizia anterioară Revizia următoare
| Fişierul intrare/ieşire: | dungeon.in, dungeon.out | Sursă | ONI 2018, clasele 11-12, ziua 2 |
| Autor | Eugenie Daniel Posdarascu | Adăugată de |  Tamio Vesa Nakajima •tamionv |
| Timp execuţie pe test | 1.25 sec | Limită de memorie | 128000 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Dungeon
Fie G un graf neorientat cu 2 ∗ N noduri și 3 ∗ N − 2 muchii. Fiecare muchie este colorată în alb, negru sau roșu.
Se garantează următoarele:
§ Există N − 1 muchii albe. Capetele lor sunt noduri din mulțimea 1, 2, . . . , N. Ele formează un
arbore.
§ Există N − 1 muchii negre. Capetele lor sunt noduri din mulțimea N + 1, N + 2, ..., 2 ∗ N.
Ele formează un arbore.
§ Există N muchii roșii. Fiecare muchie are un capăt în mulțimea 1, 2, . . . , N și celălalt capăt în
mulțimea N + 1, N + 2, ..., 2 ∗ N.
Cele 2 * N capete ale muchiilor roșii sunt distincte două câte două. Cu alte cuvinte, fiecare nod
din graf are exact o muchie roșie incidentă.
Numim ciclu hamiltonian special un ciclu care:
§ vizitează fiecare nod al grafului exact o dată.
§ nu parcurge consecutiv două muchii de aceeași culoare.
§ începe din nodul 1, iar prima muchie parcursă este de culoare roșie.
Cerinta
Afișați un ciclu hamiltonian special al grafului G sau constatați că nu există niciun astfel de ciclu.
Date de intrare
Fișierul de intrare dungeon.in va conține pe prima linie un număr natural
