Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include<bits/stdc++.h>
- using namespace std;
- #define inf (unsigned)~(0)
- vector<int> adj[110];
- vector<string> cityName;
- map<string, int> cityval;
- map<int, string> valcity;
- int color[123456]={0};
- int dis[123456]={0};
- int prev[123456]={inf};
- int tim=0;
- int f[123456]={-1};
- int low[123456]={-1};
- bool art[123456];
- void dfs_vis(int v){
- color[v]=1;
- tim++;
- dis[v]=tim;
- int child=0;
- for(int i=0;i<adj[i].size();i++){
- int w=adj[v][i];
- if(color[w]==0){
- child++;
- prev[w]=v;
- dfs_vis(w);
- low[v]=min(low[v],low[w]);
- if(prev[v]==inf&&child>1)
- art[v]=true;
- if(prev[v]!=inf&&low[w]>=dis[v])
- art[v]=true;
- }
- else if(prev[v]!=w)
- {
- if(dis[w]<low[v])
- low[v]=min(low[v],dis[w]);
- }
- }
- color[v]=2;
- tim++;
- f[v]=tim;
- }
- int main(){
- while(1){
- int n;
- cin>>n;
- if(n==0)
- break;
- for(int i=0;i<n;i++){
- string s;
- cin>>s;
- cityval[s]=i;
- valcity[i]=s;
- }
- int r;
- cin>>r;
- for(int i=0;i<r;i++){
- int s1, s2;
- cin>>s1>>s2;
- adj[cityval[s1]].push_back(cityval[s2]);
- adj[cityval[s2]].push_back(cityval[s1]);
- }
- for(int i=0;i<n;i++){
- dfs_vis(valcity[i]);
- }
- int cnt;
- for(int i=0;i<n;i++){
- if(art[i])
- cnt++;
- cout<<cnt<<" city found"<<endl;
- }
- for(int i=0;i<n;i++){
- if(art[i])
- cout<<valcity[i]<<endl;
- }
- }
- }
Add Comment
Please, Sign In to add comment