UVa 10199

From Algorithmist
Jump to: navigation, search

10199 - Tourist Guide[edit]

Summary[edit]

This is a classic Graph Theory problem of finding Articulation Point.

Explanation[edit]

All there is to the problem is finding the Articulation Point of a given graph. Use the standard algorithm.

Input[edit]

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
0

Output[edit]

City map #1: 1 camera(s) found
sugarloaf

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