ACM 1994

Tom és Jerry ugyanabban a házban laknak. Mindkettőjüknek van a házban egy kitüntetett szobája, amit az otthonuknak nevezünk. Otthonaikból kiindulva, mindketten rendszeresen sétálnak a házban. Tom pontosan akkor tud az A szobából átjutni a B szobába, ha az A-ból úgynevezett macskaátjáró nyílik a B szobába. Ezek az átjárók egyirányúak. Ehhez hasonlóan Jerry is csak akkor tud egyik szobából a másikba jutni, ha a szobák közt úgynevezett egérátjáró van. A egérátjárók is egyirányúak. Tom nem használhatja Jerry, míg Jerry nem használhatja Tom átjáróit. Írjunk programot, amely megoldja a következő részfeladatokat.
A. Határozzuk meg, hogy van-e olyan szoba, amelyben Tom és Jerry találkozhat egymással.
B. Határozzuk meg, hogy Jerry — otthonából indulva — tehet-e olyan körsétát, amely során biztosan nem találkozik Tommal!

Bemenet:

Az INPUT.TXT állomány egész számokat tartalmaz, amelyek a ház konfigurációját írják le. Az első sor három egészet tartalmaz; az első a ház szobáinak száma, a második Tom otthonának sorszáma, a harmadik Jerry otthonának sorszáma. A következő sorok mindegyike két pozitív egészet tartalmaz. Az A B pár egy macsakátjárót reprezentál az A szobából a B szobába. Az átjárók felsorolását két darab -1 zárja le. Az ezt követő sorok mindegyike ismét két pozitív egészet tartalmaz. Az A B pár egy egérátjárót reprezentál az A szobából a B szobába.

A szobák száma legfeljebb 100. A szobák sorszámozása folyamatos 1-től kezdődően.

Kimenet:

Az OUTPUT.TXT állománynak két szót kell tartalmaznia! Az első szó 'Igen', ha a házban létezik olyan szoba, amelyben Tom és Jerry találkozhat egymással. Ha ilyen szoba nincs, akkor az output 'Nem'.
A második szó 'Igen', ha Jerry — otthonából indulva — legalább két szobát érintő körsétát tud tenni úgy, hogy közben biztosan nem találkozik Tommal. Ha ilyen körséta nem létezik, akkor az output 'Nem'.

Példa:
 

INPUT.TXT	OUTPUT.TXT
5 3 5 1 2 2 1 3 1 4 3 5 2 -1 -1 1 3 2 5 3 4 4 1 4 2 4 5 5 4	Igen Igen

A hálózatokban továbbítandó üzenetek (csomagok) végtelen ciklusban "keringhetnek" az egyes csomópontok között. Ennek elkerülése végett minden csomaghoz tartozik egy TTL-érték. A TTL az angol Time To Live kifejezés rövidítése. A TTL-érték azon csomópontok számát tartalmazza, ahány csomópont továbbküldheti az üzenetet annak célállomása felé, mielőtt az üzenet visszavonhatatlanul elakad. Ha valamely csomópontba megérkezik egy üzenet, akkor annak értéke 1-gyel csökken. Ha az aktuális csomópont az üzenet célállomása, akkor a TTL érték érvénytelenné válik. Ha egy üzenet TTL értéke 0, akkor az üzenet nem küldhető tovább.
Adott néhány hálózat leírása. Minden hálózaton belül meg kell határozni azon csomópontok számát, amelyek előre adott csomópontból, előre adott TTL-értékkel nem érhetők el.

Bemenet:

Az INPUT.TXT állományban több hálózat leírása található. Minden egyes hálózat leírása egy N egész számmal kezdődik; ez a hálózatban lévő csomópontok közti kapcsolatok száma. Ha az N értéke 0, akkor az az input adatok végét jelzi. Az N értékét N darab pozitív egészekből álló számpár követi. Ezek azonosítják azokat a csomópontokat, amelyek közvetlen kommunikációs kapcsolatban állnak egymással. Minden hálózat legfeljebb 30 csomópontot tartalmaz, és bármely két csomópont között legfeljebb egy közvetlen kommunikációs összeköttetés lehetséges. A hálózati konfiguráció leírása után kérések sorozata található. Minden kérést két egész számmal kódoltunk. Az első egész egy csomópont azonosítója, a második egy üzenet lehetséges TTL-értéke. A programnak meg kell határoznia, hogy az adott csomópontból, az adott TTL-értékkel hány csúcs nem érhető el! A kéréseket két darab 0 zárja.

Kimenet:

Írjuk az eredményeket az OUTPUT.TXT nevű állományba! Minden kéréshez jelenítsük meg annak sorszámát (az első kérés sorszáma 1), az adott csomópont azonosítóját, a kezdeti TTL-értéket, valamint az el nem érthető csomópontok számát! Minden kérésre külön sorban válaszoljunk!

Példa:
 

INPUT.TXT

16 10 15  15 20  20 25  10 30  30 47  47 50  25 45  45 65 15 35  35 55  20 40  50 55  35 40  55 60  40 60  60 65 35 2  35 3  0 0 14 1 2  2 7  1 3  3 4  3 5  5 10  5 11 4 6  7 6  7 8  7 9  8 9  8 6  6 11 1 1  1 2  3 2  3 3  0 0 0

OUTPUT.TXT

Teszt #1: 5 csúcs nem érhető el a 35 csúcsból TTL=2 értékkel. Teszt #2: 1 csúcs nem érhető el a 35 csúcsból TTL=3 értékkel. Teszt #3: 8 csúcs nem érhető el a 1 csúcsból TTL=1 értékkel. Teszt #4: 5 csúcs nem érhető el a 1 csúcsból TTL=2 értékkel. Teszt #5: 3 csúcs nem érhető el a 3 csúcsból TTL=2 értékkel. Teszt #6: 1 csúcs nem érhető el a 3 csúcsból TTL=3 értékkel.

A Jack Straws egy társasjáték, amelyben néhány műanyag vagy fa pálcikát szórnak egy asztalra, és a játékosok megpróbálják egyesével felemelni azokat anélkül, hogy a többi pálcika megmozdulna. Most csak azok a pálcikák zavarják egymást, amelyek összeköthetők csatlakozó pálcikák sorozatával. Adott pálcikák végpontjainak egy listája (mintha a pálcikák egy elég nagy asztalra lennének leszórva), és el kell döntenünk, hogy néhány adott pálcika csatlakozik-e egymáshoz. Megjegyezzük, hogy érintkező vagy metsző pálcikák csatlakoznak, de két pálcika indirekt módon is csatlakozhat, más pálcikákon keresztül.

Bemenet:

Az input első sora egy n (1<n<13) egész számot tartalmaz; n az asztalon lévő pálcikák száma. A következő n sor mindegyike négy pozitív egész számot tartalmaz; x1, y1, x2, y2. Ezek egy-egy pálcika (x1, y1) és (x2, y2) végpontjainak koordinátái. Minden koordináta kisebb, mint 100. Megemlítjük, hogy a pálcikák különböző hosszúságúak is lehetnek Az inputban elsőként szereplő pálcika sorszáma 1, a másodiké 2, és így tovább. Az input fennmaradó sorai (kivéve az utolsót) két-két pozitív egész számot tartalmaz; a és b mindegyike 1 és n között lehet, beleértve a határokat is. Határozzuk meg, hogy az a és b sorszámú pálcikák csatlakoznak-e egymáshoz!
Ha a=b=0, akkor az input nem tartalmaz több sort. Feltehetjük, hogy nincs 0 hosszúságú pálcika, valamint az input adatok a leírt határokon belül vannak!

Kimenet:

Az outputnak minden (a,b) párra egy sort kell tartalmaznia, kivéve az utolsó párt, amikor is a=b=0! A sor tartalma ’Csatlakoznak’, ha az a és b pálcikák csatlakoznak egymáshoz, és ’Nem csatlakoznak’, ha az a és b pálcikák nem köthetők össze más pálcikákon keresztül. Minden pálcikát önmagához csatlakozónak tekintünk.

Példa:
 

INPUT.TXT	OUTPUT.TXT
7 1 6 3 3 4 6 4 9 4 5 6 7 1 4 3 5 3 5 5 5 5 2 6 3 5 4 7 2 1 4 1 6 3 3 6 7 2 3 1 3 0 0	Csatlakoznak Nem csatlakoznak Csatlakoznak Csatlakoznak Nem csatlakoznak Csatlakoznak