ALI JE DREVO?

 

Program

DREVO.C, DREVO.CPP, DREVO.PAS

Drevo je podatkovna struktura, ki je bodisi prazna ali pa je množica, ki jo sestavlja eno ali vec vozlišc, povezanih s povezavami (pravimo da prvo vozlišce v povezavi kaže na drugo vozlišce), ki zadošcajo naslenjim pogojem:

  1. 1. Obstaja natanko eno vozlišce, imenovano koren, v katerega ne kaže nobena usmerjena povezava.
  2. Na vsako vozlišce razen korena kaže natanko ena povezava.
  3. 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.