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.
BemenetA 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ént adjuk meg, a végpontok nevével. (Ékezet és szóköz nélküli nevek.)
KimenetA 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
A harmadik teszteset ábrája CímkékA feladat forrása: http://uva.onlinejudge.org/index.php?option=onlinejudge&page=show_problem&problem=1140
Algoritmusok: gráfbejárás, összefüggőség, elvágó pontok
megoldás |
Programozás > Feladatok >
