ALI JE DREVO?
Program |
DREVO.C, DREVO.CPP, DREVO.PAS
|
Drevo je podatkovna struktura, ki je bodisi prazna ali pa je mnoica,
ki jo sestavlja eno ali vec vozlišc, povezanih s povezavami (pravimo da
prvo vozlišce v povezavi kae na drugo vozlišce), ki zadošcajo
naslenjim pogojem:
- 1. Obstaja natanko eno vozlišce, imenovano koren, v katerega ne kae
nobena usmerjena povezava.
- Na vsako vozlišce razen korena kae natanko ena povezava.
- Obstaja enolicno zaporedje usmerjenih povezav iz korena do vsakega vozlišca.
Na spodnjih slikah so vozlišca predstavljena s krogi in pušcice predstavljajo
povezave. Prvi dve sliki predstavljata drevo, zadnja pa ne.
Danih bo vec opisov dreves. Za vsak opis moraš ugotoviti, ce predstavlja
drevo.
Vhodni podatki
Vhodne podatke sestavlja vec testnih primerov (opisov), ki jim sledi par negativnih
števil. Vsak opis sestavlja zaporedje povezav, ki jim sledi par nicel.
Vsak opis povezave je sestavljen iz para celih števil. Prvo število
oznacuje vozlišce v katerem se povezava zacne in drugo število oznacuje
vozlišce, kjer se povezava konca. Oznacbe vozlišc so vedno pozitivna
števila.
Rezultati
Za vsak opis v svojo vrsto izpiši "Primer k JE drevo.
"
oziroma "Primer k NI drevo
." kjer k
ustreza številki opisa (opisi so oštevilceni zaporedoma od 1 dalje).
Primer vhodnih podatkov
6 8 5 3 5 2 6 4
5 6 0 0
8 1 7 3 6 2 8 9 7 5
7 4 7 8 7 6 0 0
3 8 6 8 6 4
5 3 5 6 5 2 0 0
-1 -1
|
|
Pricakovan izpis
Primer 1 JE drevo.
Primer 2 JE drevo.
Primer 3 NI drevo.
|