Revizia anterioară Revizia următoare
| Fişierul intrare/ieşire: | sortop.in, sortop.out | Sursă | Algoritmiada 2016 Runda 3 Seniori |
| Autor | Adrian Budau, Eugenie Daniel Posdarascu | Adăugată de |  Adrian Budau •freak93 |
| Timp execuţie pe test | 0.25 sec | Limită de memorie | 65536 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Sortop
Se da un arbore cu N noduri. O sortare topologica a acestui arbore constituie o numerotare a celor N noduri cu valori distincte de la 1 la N, astfel incat fiecare parinte in arbore sa aibă o valoare mai mica decat fiii lui (nodul 1 este radacina, nodul N este mereu frunza).
Sarcina voastra este sa gasiti o sortare topologica valida pentru acest arbore. Aveti in schimb 2 detalii ce trebuie sa luati in considerare:
- K din cele N noduri au valoarea fixata (ordinea in sortarea topologica este prestabilita). Sarcina ramane sa completati celalalte N - K noduri.
- Valoarea rădăcinii nu este neaparat fixată.
Dandu-se arborele si cele K noduri fixate, determinati o sortare topologica valida a acestui arbore. Orice solutie este acceptata.
Date de intrare
Fişierul de intrare sortop.in va contine pe prima linie 2 numere naturale N si K. Pe urmatoarele N - 1 linii se vor afla cate 2 numere naturale X si Y reprezentand faptul ca aveti muchie de la X la Y. Urmatoarele K linii contin cate alte 2 numere naturale X si Y reprezentand faptul ca nodul X a fost numerotat cu valoarea Y.
Date de ieşire
Fişierul de ieşire sortop.out va contine pe o singura linie N numere naturale reprezentand sortarea topologica a arborelui din datele de intrare.
Restricţii
- 5 ≤ N ≤ 100.000
- 2 ≤ K ≤ N
- Pentru teste in valoare de 50 de puncte N ≤ 1000.
Exemplu
| sortop.in | sortop.out |
|---|---|
| 8 3 1 2 1 3 3 4 4 5 1 6 6 7 7 8 1 2 5 4 8 7 | 3 1 4 5 6 7 8 2 |
