Matematické Fórum

ahoj, nevíte někdo jakým algoritmem lze vyřešit tato úloha? Děkuji moc za odpověď.


Matfyzáci jsou podivná stvoření. Jedním z nejpodivnějších fenoménů, který v této komunitě lidí vzniká, je vytváření vzájemných hierarchií. Matfyzáci jsou pyšní na svoji inteligenci a davají to ostatním najevo. Nejvíc se tento problém projevuje tam, kde jsou matfyzáci nuceni tvořit fronty. Matfyzák, který si o jiném matfyzákovi myslí, že je hloupější, odmítá stát ve frontě za ním. Tím vzniká řada nepříjemných strkanic a šarvátek. Situace začíná být neúnosná, takže se přímo sám děkan obrátil na vás, zda byste problém nevyřešili...

Napište program, který dostane seznam matfyzáků a jejich názorů na inteligenci ostatích. Vašim úkolem je matfyzáky uspořádat do posloupnosti tak, aby vždy platilo, že pokud považuje matfyzák A kolegu B za hloupějšího, pak musí být v této posloupnosti stát A před B.

Nedá moc přemýšlení, že požadované uspořádání nemusí existovat. Pokud si např. A myslí, že je chytřejší než B a B si myslí, že je chytřejší než A, tak nelze vytvořit uspořádání, se kterým by byli oba spokojeni. V takovém případě oznamte, že uspořádání nelze vytvořit.

Formát dat:
Na standardním vstupu se na prvním řádku se nachází číslo N (0 ≤ N ≤ 20000) určující počet matfyzáků. Na následujících N jsou údaje o jednotlivých matfyzácích, přičemž    každý matfyzák je na samostatném řádku. Na začátku řádku je nejprve uvedeno číslo k, které pro daného matfyzáka definuje počet jeho kolegů, o kterých si myslí, že jsou hloupější, než on sám. Následuje k čísel, která představují indexy těchto kolegů (matfyzáky číslujeme od 1).

Výsledky vypište na standardní výstup jako permutaci matfyzáků (tzn. posloupnost jejich indexů) oddělovanou mezerami. Pokud není možné matfyzáky uspořádat, vypište pouze řetězec "no".

Pokud existuje správných řešení víc, stačí vypsat libovolné z nich.


Příklad 1:
Vstup:
  5
  1  4
  2  1 4
  1  4
  0
  3  3 1 2
Odpovídající výstup:
  5 3 2 1 4

Příklad 2:
Vstup:
  3
  1  2
  1  3
  1  1
Odpovídající výstup:
  no