Programozás‎ > ‎Feladatok‎ > ‎

Gyémánt öröklődés

Objektumorientált programozási nyelvekben az osztályok örökölhetnek egymástól. Az örökléseket irányított gráffal szokás ábrázolni, ha X örököl Y-tól, akkor X-ből él mutat Y-ba. A többszörös öröklődést megengedő nyelvekben merül fel a gyémánt öröklődés problémája: lehetséges, hogy D-ből két különböző öröklési lánc vezet ugyanahhoz az A osztályhoz. (Az út lehet hosszabb is, nem csak kettő hosszú.) 

Feladat

Adott öröklési gráf esetén döntsük el, hogy előfordul-e gyémánt öröklődés az osztályhierarchiában.

Bemenet

A bemenet első sora a tesztesetek T számát adja meg. Ezután T gráf leírása következik, T blokkban. Minden blokk a gráf csúcsainak N számával kezdődik. Ezután N sorban az öröklések vannak leírva. Az i. sorban azt adjuk meg, hogy az i. osztály hány osztálytól örököl (Mi) majd ugyanebben a sorban fel is soroljuk az osztályok sorszámát, akiktől az i. osztály örökölt. (Az osztályokat 1-től számozzuk.) 

Méretek

1 <= T <= 50, 0 <= Mi <= 10
Kis bemenet: 1 <= N <= 50
Nagy bemenet: 1 <= N <= 1000

Kimenet

Minden tesztesethez a Yes vagy No értéket kell kiírni (a mintának megfelelően) aszerint, hogy a megadott öröklési gráfban előfordul-e gyémánt öröklődés.

Példa

Bemenet  Kimenet
3
3
1 2
1 3
0
5
2 2 3
1 4
1 5
1 5
0
3
2 2 3
1 3
0

Case #1: No
Case #2: Yes
Case #3: Yes


Tesztadatok

Címkék

Algoritmusok: mélységi bejárás

megoldás