apraksts uzdevumi suutiit jauns statuss rezultati helps apraksts

koks Koks 1 sek.


 Uzdevums

Dots orientēts grafs ar N virsotnēm. Virsotnes ir numurētas ar naturāliem skaitļiem no 1 līdz N. Orientētu grafu sauc par koku, ja vienlaicīgi ir izpildīti sekojoši nosacījumi:

  • ir iespējams atrast tieši vienu tādu virsotni, kurā neieiet neviena šķautne (to sauc par koka sakni),
  • katrai virsotnei ir iespējams atrast tieši vienu ceļu pa šķautnēm, kas iet no saknes līdz šai virsotnei.

To škautņu kopskaitu, pa kurām jāiet, lai nonāktu līdz virsotnei, sauc par šīs virsotnes dziļumu. Par dotā koka augstumu sauc lielāko virsotnes dziļumu.

Zīmējumā redzamajos orientēto grafu piemēros kreisais un vidējais ir koki, bet labējais nav. Kreisā koka sakne ir virsotne ar numuru 5 un augstums 2, bet kokam, kas atrodas vidū, sakne ir virsotne ar numuru 6 un augstums ir 5.

Uzrakstiet programmu, kas ievadītam grafam nosaka, vai tas ir koks, un, ja ir, atrod tā sakni un augstumu!

 
 Ievaddati

Teksta faila koks.dat pirmajā rindā doti divi veseli skaitļi N(1≤N≤1000) un M(0 ≤M≤1000), kas apzīmē attiecīgi grafa virsotņu un šķautņu skaitu. Starp skaitļiem ievaddatos ir viens tukšumsimbols. Nākošajās M faila rindās ir doti grafa šķautņu apraksti - katra šķautne aprakstīta savā rindā. Katra rinda satur divus naturālus skaitļus, kas atdalīti ar tukšumsimbolu. Pirmais skaitlis ir tās virsotnes numurs, no kuras šķautne iziet, bet otrs - tās virsotnes numurs, kurā šķautne ieiet.

 
 Izvaddati

Ja ievadītais grafs ir koks, tad teksta faila koks.rez vienīgajā rindā jāizvada koka saknes numurs un augstums. Ja ievadītais grafs nav koks, faila vienīgajā rindā jāizvada divi skaitļi 0. Starp skaitļiem jābūt vienam tukšumsimbolam.

 
 Piemērs

koks.datkoks.rez
6 5
6 2
5 4
6 3
5 1
5 6
5 2
  
koks.datkoks.rez
3 3
1 2
2 3
3 1
0 0

 
 Atsauces
Uzdevums izmantots Latvijas 16.informātikas olimpiādē 2003.gadā.

Drukāšanai

 

Copyright © 2001 Girts Folkmanis, LIIS