Egy kommunikációs hálózat csomópontokból és csomópont párokat összekötő egyirányú átvitelt megvalósító közvetlen vonalakból épül fel. Azt mondjuk, hogy egy U csomópontból elérhető a V csomópont, ha U-ból lehet átvitelt megvalósítani V-be esetleg közbülső csomópontokon keresztül. A hálózatnak van egy K kitüntetett csomópontja. Az üzemeltetés szeretné tudni, hogy melyek azok a K-tól különböző X csomópontok, amelyek legfeljebb T közbülső csomópont érintésével elérhetők K-ból és X-ből akárhány csomópont érintésével elérhető K.
Feladat
Írj programot, amely kiszámítja azokat a csomópontokat, amelyek legfeljebb T közbülső csomóponton keresztül elérhetők K-ból, és amelyekből elérhető K!
Bemenet
A halozat.be szöveges állomány első sorában négy egész szám van egy-egy szóközzel elválasztva: a csomópontok száma (2<=N<=10000), a közvetlen vonalak száma (2<=M<=300000), a kitüntetett csomópont sorszáma (1<=K<=N) és a kérdésben szereplő távolság (0<=T<N). A további M sor mindegyike két U V egész számot tartalmaz egy szóközzel elválasztva, ami azt jelenti, hogy van az U csomópontból a V csomópontba átvitelt megvalósító közvetlen vonal (1<=U≠V<=N).
Kimenet
A halozat.ki szöveges állomány első sora egy egész számot tartalmazzon, azon csomópontok számát, amelyek legfeljebb T közbülső csomóponton keresztül elérhetők K-ból, és amelyekből elérhető K! A második sor ezen csomópontok sorszámát tartalmazza egy-egy szóközzel elválasztva, növekvő sorrendben.
Példa
Bemenet |
Kimenet |
10 14 3 2 2 3 1 3 3 4 3 5 1 5 4 6 6 2 6 7 7 9 9 10 5 8 8 10 5 4 5 7 | 4 2 4 5 6
|
Tesztadatok
Címkék
A feladat forrása: NTOITV 2015 2. forduló, 11-13. évfolyam
Algoritmusok: távolság irányított gráfban
megoldás |