PROBLEMA 11: PARCURGERE EULER
DEADLINE: Luni, 22 martie 1999
TIMP DE IMPLEMENTARE: 60-75 minute
DOMENIU: Parcurgeri de arbori
PUNCTAJ: 50 dexteri
(Observatie. Problema poate valora ceva mai mult
de 50 dexteri, dar s-a limitat intrarea la
dimensiuni mici, ceea ce simplifica mult
abordarea)
Fie un arbore general cu radacina (un nod poate avea oricati fii).
Arborele are N noduri numerotate de la 1 la N. O parcurgere Euler a
acestui arbore se face astfel:
- Se tipareste radacina arborelui;
- Pentru fiecare dintre fiii radacinii:
- Se parcurge dupa aceeasi metoda subarborele care are drept radacina
fiul respectiv;
- Se tipareste radacina.
De exemplu, sa consideram arborele cu 7 noduri:
5
/ \
3 7
/ | \ |
6 1 2 4
Atunci parcurgerea Euler este: 5 3 6 3 1 3 2 3 5 7 4 7 5.
Problema cere ca, dandu-se un numar N si o succesiune de numere, sa se
spuna daca succesiunea reprezinta o parcurgere Euler corecta a unui
arbore cu N noduri si, in caz afirmativ, sa se reconstituie arborele.
DATE DE INTRARE: Fisierul text EULER.IN contine datele:
N // 1<=N<=1000 (una mie)
numar numar ... numar // O succesiune de numere cuprinse intre
1 si N. Numarul de numere este necunoscut.
DATELE DE IESIRE: Fisierul text EULER.OUT va contine pe prima linie
unul din cuvintele DA sau NU, dupa cum exista sau nu un arbore a
carui parcurgere Euler sa fie tocmai succesiunea de numere data. Daca
raspunsul este afirmativ, pe urmatoarele N-1 linii se vor afisa
muchiile arborelui, in ordinea in care le exploreaza parcurgerea
Euler. Pentru fiecare muchie se vor tipari nodul parinte si nodul fiu
(in aceasta ordine), separate printr-un spatiu.
EXEMPLE:
EULER.IN EULER.OUT
7 DA
5 3 6 3 1 3 2 3 5 7 4 7 5 5 3
3 6
3 1
3 2
5 7
7 4
EULER.IN EULER.OUT
3 NU
1 2 3 1 2 3 1 2 3 1 2 3
TIMP DE RULARE: O secunda.
COMPLEXITATE: O(N)
|
|
