Elfogó
A városi rendőrség egy veszélyes bűnöző elfogását tervezi, aki gépkocsival folyamatosan közlekedik a város utcáin. A rendőrségnek korlátozottak a lehetőségei, nem tud például minden kereszteződésbe rendőrt állítani az elfogás érdekében. Ravasz őrmesternek az alábbi kitűnő ötlete támadt. Egy kijelölt K kereszteződésből indulva bejárja a város utcáit és úgy egyirányúsítja azokat, hogy a bűnöző előbb-utóbb úgyis eljut a K kereszteződésbe, ahol egy másik rendőr várakozik, aki elfogja a bűnözőt. A kapitánynak nagyon tetszik az ötlet, de kiköti, hogy Ravasz őrmesternek is be kell tartania a közlekedési szabályokat:
- A már egyirányúsított utcában az őrmester is csak a jelzett irányban közlekedhet.
- Továbbá, ha az A kereszteződésből a B-be vezető utcát akarja egyirányúsítani, azt csak úgy teheti, hogy elmegy az A-ba, ott elhelyez egy behajtani tilos táblát B irányban, ezután elmegy az utcában a B kereszteződésig és ott elhelyezi az A-irányba mutató egyirányú utca táblát.
- Ugyanazon utcában többször is járhat, de csak a már beállított irányban.
Így a megoldás egyértelműen leírható az őrmester útja során érintett kereszteződések sorozatával, mivel ha az útja során egy olyan kereszteződésbe ér, amelyből a B irányában halad tovább, akkor ha ez az utca még nem volt egyirányúsítva, akkor egyirányúsítja, egyébként csak halad tovább az utcában. A város úthálózata összefüggő, azaz minden kereszteződésből el lehet jutni bármely másik kereszteződésbe.
Feladat:
Írj programot, amely kiszámít egy olyan bejárási sorozatot, amelyet bejárva és elvégezve az egyirányúsítást, a bűnöző előbb-utóbb feltűnik abban a kereszteződésben, ahonnan az őrmester indult. Minden utcában mindkét irányban lehet közlekedni, de az utcán megfordulni tilos. Kereszteződésben azonban meg lehet fordulni. Az egyirányúsítás következtében csak az a kereszteződés lehet olyan, hogy nem indul belőle egyetlen egyirányú út sem, amelyikből az őrmester elindult.
Bemenet:
Az ELFOGO.BE állomány első sorában a kereszteződések (1<=N<=200) száma, a második sorában az utcák (1<=M<=10000) száma van. A következő M sor mindegyike egy A B számpárt (1<=A, B<=200) tartalmaz egy szóközzel elválasztva, ami azt jelenti, hogy az A kereszteződésből megy egy (kétirányú) utca a B kereszteződésig. Két kereszteződés között legfeljebb egy utca lehet.
Kimenet:
Az ELFOGO.KI állomány első sorába az őrmester bejáró útját megadó kereszteződések L számát, a második sorba pedig a bejárt L kereszteződés sorszámát kell írni, egy-egy szóközzel elválasztva.
Példa:
| ELFOGO.BE | ELFOGO.KI |
| 7
10
1 2
1 3
1 4
2 5
2 6
3 7
1 6
2 3
3 4
2 7 |
21
1 2 3 4 3 7 3 2 5 2 6 2 7 2 1 3 1 4 1 6 1 |
Megj.: a hivatalos archívumban lévő példát hibásnak találtuk...
Tesztadatok
elfogo.zip
Ellenőrző program:
elfchk2.pas (Az
elfogo.beX,
elfogo.k_X bemenet és kimeneti fájlokat veti össze. X megadható paraméterként vagy indítás után.)
