[UVA][cutpoint][關節點][dfs] 10199 - Tourist Guide
Problem F: Tourist Guide
| 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) foundWhere 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;
}