Fa (Tree)

A jól ismert adatstruktúra, amely lehet üres vagy halmaza egy vagy több pontnak, amelyek élekkel kapcsolódnak egymáshoz, kielégítve az alábbi feltételeket.

·         Pontosan egy - gyökérnek nevezett - pont van, amelybe nem érkezik él.

·         A gyökeret kivéve, minden csúcsba pontosan egy él mutat.

·         A gyökérből minden csúcsba pontosan egy irányított élsorozaton át lehet eljutni.

Például tekintsük az alábbi illusztrációt, amelyen a csúcsokat körök, az éleket pedig nyilak helyettesítik. Az első kettő fa, a harmadik nem az.

Feladat:

Írj programot, amely a csúcsok és a köztük lévő irányított élek ismeretében megadja, hogy a struktúra definíció szerint fa vagy sem.

Bemenet:

A bemeneti állomány N tesztesetet tartalmaz. Az első sorban az N értéke szerepel. Minden teszteset első sorában egy K pozitív egész áll. A következő sorban K darab számpár található, amelyek mindegyike egy-egy irányított élet reprezentál. A számpár első tagja azt a csúcsot adja meg, amelyből az él indul, a másik szám pedig azt, amelybe mutat. A csúcsok száma minden esetben nullánál nagyobb.

Kimenet:

Minden tesztesetre a "k fa" vagy a "k nem fa" üzenetek közül a megfelelőt kell írni a kimeneti állományba, ahol k a teszteset sorszámát jelenti.

Példa:

 

 

(ACM ELTE csapatverseny 2000)