Informatika gyűjtemény

Egy szinttel feljebb Hálózat

2004050607080910

NézetNyomtat

Hálózat

Egy számítógépes hálózat csomópontokból és bizonyos csomópont-párokat összekötő egyirányú adatátvitelt biztosító közvetlen vonalakból épül fel. Adott $A$ csomópontból egy másik $B$ csomópontba lehet adatot továbbítani, ha van olyan $A=p_1, p_2, \ldots, p_k=B$ csomópont-sorozat, hogy minden $i$-re ($i=1,\ldots,k-1$) $p_i$ –ből van közvetlen vonal $p_{i+1}$ –be.

Feladat

Készíts programot (HALOZAT.PAS, ...), amely kiszámítja, hogy melyek azok a $Q$ csomópontok, amelyekbe lehet adatot továbbítani adott $K~$ csomópontból, de $Q$-ból nem lehet adatot továbbítani $K$-ba!

Bemenet

A HALOZAT.BE szöveges állomány első sorában három egész szám van, a csomópontok $N$ ($2\leq N\leq 150$) száma, és a közvetlen vonalak $M$ száma és a kijelölt $K$ csomópont. A csomó­pontokat az $1,\ldots, N$ számokkal azonosítjuk. A további $M$ sor mindegyike egy $U ~ V$ $(1\leq U, V\leq N)$ számpárt tartalmaz, ami azt jelenti, hogy az $U$ csomópontból közvetlen vonalon lehet adatot továbbítani a $V$ csomópontba.

Kimenet

A HALOZAT.KI szöveges állomány első sorába azon $Q$ csomópontok számát kell írni, amelyekbe lehet adatot továbbítani a $K$ csomópontból, de $Q$-ból nem lehet adatot továbbítani $K$-ba! A második sor tartalmazza ezeket a csomópontokat tetszőleges sorrendben, egy-egy szóközzel elválasztva!

Példa

HALOZAT.BEHALOZAT.KI
10 15 5
4 5
2 4
4 1
5 2
5 6
6 5
6 2
6 7
1 3
3 9
1 9
7 8
8 9
9 10
8 10
6
1 7 3 8 9 10

Tesztadatok