Az S. 13. feladat (2005. december)

S. 13. Két játékos egy bábuval felváltva lépked egy irányított gráf csúcsain. Aki nem tud lépni, mert az aktuális helyről nem indul ki él, veszít, és az ellenfél nyer. Ha a bábu harmadszor kerül ugyanarra a mezőre, a játék eredménye döntetlen. Írjunk programot, ami a gráf mindegyik csúcsáról eldönti, hogy onnan indulva mi a legjobb eredmény, amit a kezdő biztosan el tud érni.

A programot a parancssorból fogjuk futtatni két paraméterrel, amelyek az input, illetve output fájl nevét tartalmazzák. Az input fájl fogja tartalmazni a gráfot. Az output fájlban kell felsorolni, hogy az egyes mezők nyerők vagy vesztők.

Az input fájl első sorában a csúcsok és az élek száma (n,m) fog állni. A csúcsokat számozzuk 1-től n-ig. A további m sor egy-egy irányított él kezdő-, illetve végpontjának sorszámát tartalmazza. Az output fájl n sorból álljon; az i-edik sor tartalma legyen N, D vagy V attól függően, hogy az i-edik csúcsból indulva a kezdő játékosnak nyerő stratégiája van, mindkét játékosnak van döntetlen stratégiája, vagy a második játékosnak van nyerő stratégiája.

Feltételezhetjük, hogy a gráfnak legfeljebb csúcsa és legfeljebb éle van.

Példa: a programot az s13 graf.txt eredmeny.txt paranccsal futtatjuk.

Beküldendő a program forráskódja (s13.pas, s13.cpp, ...).

(10 pont)

A beküldési határidő 2006. január 16-án LEJÁRT.

Statisztika:

7 dolgozat érkezett.
10 pontot kapott:	Homolya Miklós, Nikházy László.
4 pontot kapott:	2 versenyző.
2 pontot kapott:	2 versenyző.
1 pontot kapott:	1 versenyző.

A KöMaL 2005. decemberi informatika feladatai