Programozás‎ > ‎Feladatok‎ > ‎

Verseny (OKTV)

Egy kieséses versenyben ismerjük a csapatok mérkőzéseit: ki kit győzött le.

Feladat

Írj programot, amely megadja:
A. azt a csapatot, amely a kiesettek közül a legtöbbször győzött;
B. a legtöbb csapatot közvetlenül vagy közvetve legyőző csapatot;
C. a következő mérkőzést játszó két csapatot, amely két olyan versenyben levő csapat legyen, amely eddig közvetve vagy közvetlenül a lehető legkevesebb csapatot győzte le!

Bemenet

A verseny.be szöveges állomány első sorában a csapatok száma (2<=N<=1000) és a mérkőzések száma van (1<=M<N), egy szóközzel elválasztva. A következő M sor mindegyikében két csapat I és J sorszáma van (1<=I≠J<=N), ami azt jelenti, hogy az I-edik csapat legyőzte a J-edik csapatot.

Kimenet

A verseny.ki szöveges állomány első sorába a kiesettek közül legtöbb győzelmet szerző csapat sorszámát kell írni (-1-et, ha nincs ilyen csapat)! A második sorba azt a csapatot, amely a legtöbb más csapatot győzte le közvetve vagy közvetlenül, a harmadik sorba a szabály szerint a következő mérkőzést játszó két csapat sorszámát, egy szóközzel elválasztva! Ha több megoldás van, bármelyik kiírható, a harmadik sorban az egyetlen -1 szám álljon, ha nincs megoldás!

Példa

Bemenet  Kimenet
8 5
1 2
4 3
4 1
7 8
5 6
1
4
5 7


Tesztadatok

Címkék

A feladat forrása: NTOITV 2012 2. forduló, 11-12. évfolyam
Algoritmusok:

megoldás