unlucky_13

uva_10199

May 24th, 2013
46
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.44 KB | None | 0 0
  1. /*
  2.  Author                             :     unlucky_13
  3.  Problem_link                       :
  4.  Category                           :
  5.  Algorithm_Used                     :
  6.  *
  7.  */
  8.  
  9. #include<cstdio>
  10. #include<sstream>
  11. #include<cstdlib>
  12. #include<cctype>
  13. #include<cmath>
  14. #include<algorithm>
  15. #include<set>
  16. #include<queue>
  17. #include<stack>
  18. #include<list>
  19. #include<iostream>
  20. #include<fstream>
  21. #include<numeric>
  22. #include<string>
  23. #include<vector>
  24. #include<cstring>
  25. #include<map>
  26. #include<iterator>
  27. #define LL long long int
  28. //const long long int inf = 2147483647 ;
  29. //const int minx=;
  30. const int maxn=200;
  31.  
  32. using namespace std;
  33. vector<int>to[maxn];
  34. int dfsn[maxn],low[maxn],tim,n,art[maxn],ans,e,root;
  35. map<string,int>M ;
  36. string MM[maxn] ;
  37. void reset(){
  38.    
  39.         for(int i=0;i<=n;i++) to[i].clear();
  40.         M.clear() ;
  41.         tim=0;
  42.         ans = 0 ;
  43.         memset(art,0,sizeof(art)) ;
  44.         memset(dfsn,-1,sizeof(dfsn)) ;
  45.         memset(low,0,sizeof(low)) ;
  46.    
  47. }
  48.  
  49. void DFS(int u,int p)
  50. {
  51.    
  52.     dfsn[u]=low[u]=tim++;
  53.     int ch = 0 ;
  54.     for(int i=0;i<(int)to[u].size();i++)
  55.     {
  56.         int v=to[u][i];
  57.         if(dfsn[v]==-1){
  58.             ch++ ;
  59.             DFS(v,u);
  60.             low[u]=min(low[u],low[v]);
  61.             if(dfsn[u]>0 && low[v]>=dfsn[u]) art[u]=1 ;
  62.  
  63.         }
  64.        
  65.         else if(v!=p)low[u]=min(low[u],dfsn[v]);
  66.  
  67.     }
  68.     if(dfsn[u]==0 && ch>1) art[u]=1 ;
  69.    
  70. }
  71.  
  72. int main() {
  73.  
  74.     freopen("C:\\Users\\Mazhar\\Desktop\\Text_Files\\in.txt", "r", stdin);
  75.    
  76.     string city1,city2 ;
  77.     int ct=0 ;
  78.     while(1){
  79.         scanf("%d",&n) ;
  80.         if(!n) break ;
  81.         if(ct) cout<<endl ;
  82.         reset() ;
  83.         for(int i=0;i<n;i++) {
  84.             cin>>city1 ;
  85.            // M[city1]=i ;
  86.             MM[i]=city1 ;
  87.            
  88.         }
  89.         sort(MM,MM+n) ;
  90.         for(int i=0;i<n;i++) {
  91.             M[MM[i]]=i ;
  92.         }
  93.        
  94.         scanf("%d",&e) ;
  95.         while(e--){
  96.             cin>>city1>>city2 ;
  97.             int u = M[city1]  ;
  98.             int v = M[city2] ;
  99.             to[u].push_back(v) ;
  100.             to[v].push_back(u) ;
  101.         }
  102.        
  103.          for(int i=0;i<n;i++){
  104.             if(dfsn[i]==-1) {
  105.                     tim = 0 ;
  106.                     DFS(i,-1);
  107.                 }
  108.         }
  109.         for(int i=0;i<n;i++){
  110.             ans+=art[i] ;
  111.         }
  112.         printf("City map #%d: %d camera(s) found\n",++ct,ans) ;
  113.        
  114.         for(int i=0;i<n;i++){
  115.             if(art[i]) cout<<MM[i]<<endl ;
  116.         }
  117.        
  118.        
  119.     }
  120.    
  121.    
  122.     return 0;
  123.  
  124. }
Advertisement
Add Comment
Please, Sign In to add comment