ŠKOLSKO NATJECANJE 2014. / Srednja škola, II. podskupina (3. i 4. razred) - 3. zadatak

Perica je direktor poznate kompanije “Stablo” koja se bavi prodajom papira. Kompanija zapošljava ukupno N ljudi označenih prirodnim brojevima redom od 1 do N, gdje je Perica označen brojem 1. Neki zaposlenici imaju sebi izravno podređene radnike, i to najviše dva - svoju lijevu i desnu ruku. Svaki radnik je izravno podređen točno jednoj osobi (osim Perice koji je direktor) i svaki radnik je izravno ili neizravno podređen Perici. Drugim riječima, hijerarhija kompanije čini stablo u kojem je Perica na vrhu, svaki čvor ima najviše dva djeteta od kojih je jedno lijevo dijete a drugi desno dijete.

Slika 1: Hijerarhija u kompaniji koja odgovara trećem primjeru dolje Kompanija se nedavno našla u problemima i sada Pericu zanima popis svih zaposlenih poredanih po moći (kako bi znao na koga svaliti krivnju). Kako bi za neka dva radnika A i B odredio tko je moćniji, Perica se služi sljedećim pravilima:

1. Perica (zaposlenik broj 1) ima najveću moć.
2. Ukoliko je izravni nadređeni radniku A moćniji od izravnog nadređenog radniku B, tada je radnik A moćniji od radnika B (i obrnuto).
3. Ukoliko A i B imaju zajedničkog izravnog nadređenog, tada je njegova desna ruka moćnija od njegove lijeve ruke. Primijetite da ovako zadana pravila jedinstveno definiraju poredak moći u cijeloj organizaciji. Na primjer, ukoliko je organizacija ilustrirana dijagramom sa slike, tada strelice prikazuju izravno podređene zaposlenike, a zaposlenik nacrtan desno predstavlja desnu ruku svoga izravno nadređenog. U ovom je slučaju popis zaposlenika poredan po moći [1, 8, 13, 11, 6, 3, 12, 2, 9, 7, 5, 10, 4]. Napišite program koji će, na temelju podatka o nadređenosti zaposlenika, odrediti poredak zaposlenika po moći.

ULAZNI PODACI

U prvom redu nalazi se prirodan broj N (1 ≤ N ≤ 20), broj zaposlenika u kompaniji. U sljedećih N redova nalaze se po dva prirodna broja. U K-tom od tih N redova nalaze se cijeli brojevi LK, RK (0 ≤ LK, RK ≤ N), lijeva i desna ruka K-tog zaposlenika. Neki (ili oba) od ta dva broja mogu biti 0, što označava da taj zaposlenik nema svoju izravno podređenu lijevu ili desnu ruku. Ulazni podaci će biti takvi da hijerarhija odgovara opisu iz teksta zadatka (svako ima točno jednog nadređenog, svi su izravno ili neizravno podređeni zaposleniku 1).

IZLAZNI PODACI

U prvi i jedini red izlaza potrebno je ispisati N prirodnih brojeva odvojenih jednim razmakom – zaposlenike poredanih po moći od najmoćnijeg prema najmanje moćnom.

PRIMJERI TEST PODATAKA

ulaz

3
2 3
0 0
0 0

izlaz

1 3 2

ulaz

4
2 3
0 0
0 4
0 0

izlaz

1 3 2 4

ulaz

13
13 8
10 0
0 0
0 0
0 4
7 9
0 0
6 11
0 0
0 0
0 2
0 5
12 3

izlaz

1 8 13 11 6 3 12 2 9 7 5 10 4