Informatika gyűjtemény

Egy szinttel feljebb Idegenvezetés

2004050607080910

<<  10. óra - Szélességi és mélységi bejárás  >>

<<  Idegenvezetés  >>

NézetNyomtat

Idegenvezetés (Megoldás)
Címkék > Feladat
Elmélet > Algoritmusok > Gráfalgoritmusok

Idegenvezetés

Rio de Janeiro egy gyönyörű város, de annyira sok látnivaló van, hogy az szinte kimerítő. Szerencsére barátod - Brúnó - megígérte, hogy idegenvezetőd lesz, és megmutatja a legérdekesebb helyeket.
Sajnos Brúnó nem vezet jól, gyakran bírságolják meg kisebb-nagyobb közlekedési vétségekért. Ezért jó lenne tudni, merre vannak a térfigyelő kamerák a városban, hogy azokon a kereszteződéseken óvatosan hajtsatok át. Tudni lehet, hogy a kamerákat stratégiailag kiemelten fontos pontokon helyezték el, ott ahol feltétlen át kell haladni, ha a város egyik zónájából egy másikba akarunk utazni. Egy C ponton akkor van kamera, ha van olyan A és B pont, amelyek között bármely út áthalad a C ponton.
Például az alábbi "térképen" C-ben van az egyetlen megfigyelő kamera.

Feladat

Írj programot, ami a térkép beolvasása után megadja a térfigyelő kamerák számát és helyét.

Bemenet

A bemenet több térképet tartalmazhat. Minden térkép a csomópontok N számával kezdődik (2 < N <= 100), majd a pontok neve következik soronként. Utána az utak R száma jön, minden út kétirányú, és mindegyik két csomópontot köt össze. Az utak végpontjait soronkét adjuk meg, a végpontok nevével. (Ékezet és szóköz nélküli nevek.)

Kimenet

A kimenetben üres sorokkal elválasztva adjuk meg a válaszokat. Minden térképhez írjuk ki a kamerák számát, majd a kamerák helyét.

Példa

BEKI
6
sugarloaf
maracana
copacabana
ipanema
corcovado
lapa
7
ipanema copacabana
copacabana sugarloaf
ipanema sugarloaf
maracana lapa
sugarloaf maracana
corcovado sugarloaf
lapa corcovado
5
guanabarabay
downtown
botanicgarden
colombo
sambodromo
4
guanabarabay sambodromo
downtown sambodromo
sambodromo botanicgarden
colombo sambodromo
16
a
b
c
d
e
f
g
h
i
j
k
l
m
n
o
p
20
a b
a c
c b
c d
d e
d f
d g
e f
f g
g h
h i
h l
h j
j k
l m
l n
l o
m n
n o
o p
0
 City map #1: 1 camera(s) found
sugarloaf

City map #2: 1 camera(s) found
sambodromo

City map #3: 7 camera(s) found
c d g h j l o

A harmadik teszteset ábrája