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 | 
2004-2016 BDG algoritmus szakkör