SHOW:
|
|
- or go back to the newest paste.
| 1 | #include<bits/stdc++.h> | |
| 2 | using namespace std; | |
| 3 | #define inf (unsigned)~(0) | |
| 4 | vector<int> adj[110]; | |
| 5 | vector<string> cityName; | |
| 6 | map<string, int> cityval; | |
| 7 | map<int, string> valcity; | |
| 8 | int color[123456]={0};
| |
| 9 | int dis[123456]={0};
| |
| 10 | int prev[123456]={inf};
| |
| 11 | int tim=0; | |
| 12 | int f[123456]={-1};
| |
| 13 | int low[123456]={-1};
| |
| 14 | bool art[123456]; | |
| 15 | ||
| 16 | ||
| 17 | void dfs_vis(int v){
| |
| 18 | color[v]=1; | |
| 19 | tim++; | |
| 20 | dis[v]=tim; | |
| 21 | int child=0; | |
| 22 | for(int i=0;i<adj[i].size();i++){
| |
| 23 | int w=adj[v][i]; | |
| 24 | if(color[w]==0){
| |
| 25 | child++; | |
| 26 | prev[w]=v; | |
| 27 | dfs_vis(w); | |
| 28 | ||
| 29 | low[v]=min(low[v],low[w]); | |
| 30 | if(prev[v]==inf&&child>1) | |
| 31 | art[v]=true; | |
| 32 | if(prev[v]!=inf&&low[w]>=dis[v]) | |
| 33 | art[v]=true; | |
| 34 | ||
| 35 | } | |
| 36 | else if(prev[v]!=w) | |
| 37 | {
| |
| 38 | if(dis[w]<low[v]) | |
| 39 | low[v]=min(low[v],dis[w]); | |
| 40 | } | |
| 41 | } | |
| 42 | color[v]=2; | |
| 43 | tim++; | |
| 44 | f[v]=tim; | |
| 45 | ||
| 46 | } | |
| 47 | int main(){
| |
| 48 | while(1){
| |
| 49 | int n; | |
| 50 | cin>>n; | |
| 51 | if(n==0) | |
| 52 | break; | |
| 53 | for(int i=0;i<n;i++){
| |
| 54 | string s; | |
| 55 | cin>>s; | |
| 56 | cityval[s]=i; | |
| 57 | valcity[i]=s; | |
| 58 | } | |
| 59 | int r; | |
| 60 | cin>>r; | |
| 61 | for(int i=0;i<r;i++){
| |
| 62 | int s1, s2; | |
| 63 | cin>>s1>>s2; | |
| 64 | adj[cityval[s1]].push_back(cityval[s2]); | |
| 65 | adj[cityval[s2]].push_back(cityval[s1]); | |
| 66 | } | |
| 67 | for(int i=0;i<n;i++){
| |
| 68 | dfs_vis(valcity[i]); | |
| 69 | } | |
| 70 | int cnt; | |
| 71 | for(int i=0;i<n;i++){
| |
| 72 | if(art[i]) | |
| 73 | cnt++; | |
| 74 | cout<<cnt<<" city found"<<endl; | |
| 75 | } | |
| 76 | for(int i=0;i<n;i++){
| |
| 77 | if(art[i]) | |
| 78 | cout<<valcity[i]<<endl; | |
| 79 | } | |
| 80 | } | |
| 81 | ||
| 82 | ||
| 83 | } |