Problem F: Tourist Guide

The Problem

Rio de Janeiro is a very beautiful city. But there are so many placesto visit that sometimes you feel a bit lost. But don't worry, because your friend Bruno promised youto be your tourist guide. The problem is that he is not a very good driver, as he can't see verywell (poor Bruno).

Because of his disabilities, Bruno have a lot of fines to pay and he doesn't want to have evenmore 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 candrive more carefully when passing by them.

Those cameras are strategically distributed over the city, in locations that a driver must passthrough in order to go from one zone of the city to another. In order words, if there are twocity locations A and B such that to go from one to another (A to B or B to A) a driver mustpass 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 becauseto go from A to E, for instance, you must pass through C. In this configuration, there's onlyone camera (on C).

Your task is to help Bruno (as he wants to be a musician and he doesn't want to get even closeof computers) and write a program which will tell him where are all the cameras, given themap 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 aninteger N (2 < N <= 100) which stands for the total locations of the city. Then willfollow N different place names, one per line. Each place name will have at least one and at most 30characters (all of them will be lowercase latin letters). Then will follow a non-negative integer Rwhich stands for the total routes of the city. Then will follow R lineswith the routes. Each route will be represented by the name of both places that the routeconnects (remember that the routes are bidirectional). Location names in route descriptionwill 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) found

Where d stands for the city map number (starting from 1) and c stands for the total numberof cameras. Then should follow c lines with the location names where are each camera (inalphabetic 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.

最近才開始上這一方面的課程，名詞的定義好像是使用 dfs 走訪後，找尋 back edge。
而這些 back edge 返回的深度將影響是不是關節點。
而起始點是不是關節點的判定要特別判斷。

#include <stdio.h>
#include <map>
#include <set>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
vector<int> g[105];
map<string, int> R;
set<string> S;
int visited[105], depth[105];
char buf[105], name[105][105];
int dfs(int nd, int dep, int p, int root) {
    depth[nd] = dep;
    visited[nd] = 1;
    int i, back = 0xffff, tmp, son = 0;
    bool cntpoint = false;
    for(i = 0; i < g[nd].size(); i++) {
        if(visited[g[nd][i]] == 0) {
            tmp = dfs(g[nd][i], dep+1, nd, root);
            if(tmp >= dep)  cntpoint = true;
            son++;
            back = min(back, tmp);
        } else {
            if(g[nd][i] != p)
                back = min(back, depth[g[nd][i]]);
        }
    }
    if((nd == root && son > 1)
        || (nd != root && cntpoint)) {
        S.insert(name[nd]);
    }
    return back;
}
int main() {
    int n, m, i, j, x, y, cases = 0;
    while(scanf("%d", &n) == 1 && n) {
        R.clear();
        S.clear();
        for(i = 0; i < n; i++) {
            scanf("%s", name[i]);
            R[name[i]] = i;
            g[i].clear();
            visited[i] = depth[i] = 0;
        }
        scanf("%d", &m);
        while(m--) {
            scanf("%s", buf);
            x = R[buf];
            scanf("%s", buf);
            y = R[buf];
            g[x].push_back(y);
            g[y].push_back(x);
        }
        for(i = 0; i < n; i++) {
            if(visited[i] == 0) {
                dfs(i, 1, -1, i);
            }
        }
        if(cases)   puts("");
        printf("City map #%d: %d camera(s) found\n", ++cases, S.size());
        for(set<string>::iterator it = S.begin();
            it != S.end(); it++)
            cout << *it << endl;
    }
    retrn 0;
}