thorpedosg

Untitled

Aug 6th, 2018
39
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  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. }
Add Comment
Please, Sign In to add comment