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. |
(ACM regionális verseny 1994)