|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 |
#include <iostream> #include <cstdio> #include <vector> #include <sstream> #include <string> #include <algorithm> #include <queue> #include <cstring> #include <map> #include <set> using namespace std; map<string,int> mp; map<int,string> mp2; vector<int> gr[105]; //vector<int> V; bool visit[105]; bool ap[105]; int discTime[105]; int low[105]; int par[105]; int cnt; set<string> SET; void cutvertex(int u) { static int dsc_time=0; low[u]=discTime[u]=dsc_time++; visit[u]=1; int child=0; for(int i=0;i<gr[u].size();i++) { int v = gr[u][i]; if(visit[v]==0) { par[v]=u; child++; cutvertex(v); low[u]=min(low[u],low[v]); if(par[u]==-1 && child>1) { if(ap[u]==0) { ap[u]=1; SET.insert(mp2[u]); cnt++; } } else if(low[v]>=discTime[u] && par[u]!=-1) { if(ap[u]==0) { ap[u]=1; SET.insert(mp2[u]); cnt++; } } } else if(v!=par[u]) { low[u]=min(low[u],discTime[v]); } } } int main() { string s,s2; int N,R; int kase=1; bool flag=0; while(scanf("%d",&N),N) { mp.clear(); mp2.clear(); cnt=0; for(int i=0;i<105;i++) { gr[i].clear(); visit[i]=0; ap[i]=0; par[i]=-1; discTime[i]=0; low[i]=0; } for(int i=1;i<=N;i++) { cin>>s; mp2[i]=s; mp[s]=i; } cin>>R; for(int i=1;i<=R;i++) { cin>>s>>s2; gr[mp[s]].push_back(mp[s2]); gr[mp[s2]].push_back(mp[s]); } SET.clear(); for(int i=1;i<=N;i++) { if(visit[i]==0) cutvertex(i); } if(flag) cout<<"\n"; flag=1; cout<<"City map #"<<kase++<<": "<<cnt<<" camera(s) found\n"; for(set<string>::iterator it=SET.begin();it!=SET.end();++it) { cout<<*it<<"\n"; } } return 0; } |