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ú.) ![]() FeladatAdott ö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.
BemenetA 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éretek1 <= T <= 50, 0 <= Mi <= 10 Kis bemenet: 1 <= N <= 50 Nagy bemenet: 1 <= N <= 1000 KimenetMinden 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
Tesztadatok
CímkékA feladat forrása: https://code.google.com/codejam/contest/1781488/dashboard#s=p0&a=0
Algoritmusok: mélységi bejárás
megoldás |
Programozás > Feladatok >