5. naloga
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.