ACM RTK - 1. skupina

V Afganistan!

Imamo n vojakov, oštevilčenih s števili od 0 do n−1. Med njimi vlada stroga hierarhija: nekaj vojakov ima najvišji možen čin (in jim ni nihče nadrejen), vsak od preostalih vojakov pa ima natanko enega neposredno nadrejenega vojaka.
Nekatere od vojakov — recimo jim gajstni — želimo poslati v Afganistan. Kateremu koli vojaku (gajstnemu ali ne) lahko damo ukaz, naj se odpravi, in bo to seveda naredil, pri tem pa bo s seboj odpeljal tudi vse sebi podrejene vojake. Za primer glej sliko: vsaka točka predstavlja vojaka, vojaki z višjimi čini so narisani višje. Gajstni vojaki so pobarvani črno. Če damo ukaz vojaku, označenemu s puščico, bo s seboj v Afganistan odpeljal še preostale tri vojake iz črtkano obrobljenega območja.

Na primeru s slike se očitno ne da izdati enega samega ukaza, s katerim bi poslali na pot vse gajstne vojake. Tudi dva ukaza ne zadoščata; lahko pa to naredimo s tremi ukazi, celo na dva različna načina. Zanima nas, koliko ukazov potrebujemo v splošnem.

Napiši program, ki kot podatke dobi opis vojaške hierarhije ter gajstnih vojakov in vrne najmanjše število ukazov, s katerim lahko dosežemo, da bodo v Afganistan od- potovali vsi gajstni vojaki. Če pri tem na pot ukažemo še kakšnim ne-gajstnim vojakom, ni nič narobe. Za dostop do podatkov uporabi naslednji funkciji:

• Nadrejeni(i), ki vrne zaporedno številko vojaka, neposredno nadrejenega vojaku i, oziroma −1, če ima vojak i najvišji možen čin in mu ni nihče nadrejen;
• Gajsten(i), ki vrne 1, če je vojak i gajsten (in ga torej moramo poslati v Afganistan), in 0 sicer.

Predpostavi še, da je na voljo spremenljivka n, ki vsebuje število vseh vojakov.

PDF besedilo.