Problem F: Tourist Guide
| Problem F: Tourist Guide |
The Problem
Rio de Janeiro is a very beautiful city. But there are so many places to visit that sometimes you feel a bit lost. But don't worry, because your friend Bruno promised you to be your tourist guide. The problem is that he is not a very good driver, as he can't see very well (poor Bruno).Because of his disabilities, Bruno have a lot of fines to pay and he doesn't want to have even more to pay, even though he promised you to be your tourist guide. What he would like to know, however, is where are all the cameras that help the police to fine the bad drivers, so he can drive more carefully when passing by them.
Those cameras are strategically distributed over the city, in locations that a driver must pass through in order to go from one zone of the city to another. In order words, if there are two city locations A and B such that to go from one to another (A to B or B to A) a driver must pass through a location C, then C will have a camera.
For instance, suppose that we have 6 locations (A, B, C, D, E and F) and that we have 7 routes (all of them bidirectonal) B-C, A-B, C-A, D-C, D-E, E-F and F-C. There's a camera on C because to go from A to E, for instance, you must pass through C. In this configuration, there's only one camera (on C).
Your task is to help Bruno (as he wants to be a musician and he doesn't want to get even close of computers) and write a program which will tell him where are all the cameras, given the map of the city, so he can be your tourist guide and avoid further fines.
The Input
The input will consist on an arbitrary number of city maps. Each city map will begin with an integer N (2 < N <= 100) which stands for the total locations of the city. Then will follow N different place names, one per line. Each place name will have at least one and at most 30 characters (all of them will be lowercase latin letters). Then will follow a non-negative integer R which stands for the total routes of the city. Then will follow R lines with the routes. Each route will be represented by the name of both places that the route connects (remember that the routes are bidirectional). Location names in route description will always be valid and there will be no route from one place to itself. You must read until N = 0, and this input should not be processed.The Output
For each city map you must print the line:City map #d: c camera(s) foundWhere d stands for the city map number (starting from 1) and c stands for the total number of cameras. Then should follow c lines with the location names where are each camera (in alphabetic order). You should print a blank line between output sets.
Sample Input
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
Sample Output
City map #1: 1 camera(s) found sugarloaf City map #2: 1 camera(s) found sambodromo
© 2001 Universidade do Brasil (UFRJ). Internal Contest 2001.
Articulation point
#include<stdio.h>
#include<cstring>
#include<string>
#include<vector>
#include<algorithm>
#include<map>
#define REP(i, b, n) for (int i = b; i < n; i++)
#define rep(i,n) REP(i, 0, n)
#define DBG 0
using namespace std;
int N,lbl[100],num,cases=1,parent[100];
vector<int>egs[100];
map<string,int>mp;
vector<string>name;
bool trav[100],arti[100];
void find(int root, int a){
if(DBG)printf("find %d parent %d\n",a,parent[a]);
int b,child=0,m=101;
bool ap=0;
lbl[a]=num++,trav[a]=1;
rep(i,egs[a].size()){
b=egs[a][i];
if(!trav[b]){
child++;
parent[b]=lbl[a],find(root,b);
if(parent[b]>=lbl[a])ap=1;
m=min(parent[b],m);
}
else if(lbl[b]<parent[a]){
if(DBG)printf("find old %d\n",b);
parent[a]=lbl[b];
}
}
if(DBG)printf("a m %d %d\n",a,m);
if(m<parent[a])parent[a]=m;
if(a==root&&child>1||a!=root&&ap){if(DBG)printf("arti: %d\n",a);arti[a]=1;}
}
void ans(){
vector<string>res;
memset(parent,0,sizeof(parent));
memset(arti,0,sizeof(arti));
memset(trav,0,sizeof(trav));
num=0;
int tot=0;
rep(i,N)if(!trav[i])find(i,i);
rep(i,N)if(arti[i])tot++,res.push_back(name[i]);
printf("City map #%d: %d camera(s) found\n",cases++,tot);
if(name.size()){
sort(res.begin(),res.end());
rep(i,res.size())printf("%s\n",res[i].c_str());
}
}
int main(){
char chs[40],chs2[40];
int a,b,m,n=0;
bool ll=0;
while(scanf("%d",&N)==1){
if(N==0)break;
n=0,name.clear(),mp.clear();
rep(i,100)egs[i].clear();
rep(i,N)scanf("%s",chs),mp[chs]=n++,name.push_back(chs);
scanf("%d",&m);
rep(i,m){scanf("%s%s",chs,chs2),a=mp[chs],b=mp[chs2],
egs[a].push_back(b),egs[b].push_back(a);if(DBG)printf("%d-%d\n",a,b);}
if(ll)printf("\n");ll=1;
ans();
}
}
Figure 1: Critical links
, specifies the number of direct connections of serverk and the servers which are directly connected to serverk. Servers are represented by integers from 0 to 
. Input data are correct. The first data set from sample input below corresponds to the network in figure 1, while the second data set specifies an empty network.