View difference between Paste ID: 5jKwuUAM and 2y9erM0U
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
}