10199

#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;
}

 

Leave a Reply

Your email address will not be published. Required fields are marked *