Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- /*
- Author : unlucky_13
- Problem_link :
- Category :
- Algorithm_Used :
- *
- */
- #include<cstdio>
- #include<sstream>
- #include<cstdlib>
- #include<cctype>
- #include<cmath>
- #include<algorithm>
- #include<set>
- #include<queue>
- #include<stack>
- #include<list>
- #include<iostream>
- #include<fstream>
- #include<numeric>
- #include<string>
- #include<vector>
- #include<cstring>
- #include<map>
- #include<iterator>
- #define LL long long int
- //const long long int inf = 2147483647 ;
- //const int minx=;
- const int maxn=200;
- using namespace std;
- vector<int>to[maxn];
- int dfsn[maxn],low[maxn],tim,n,art[maxn],ans,e,root;
- map<string,int>M ;
- string MM[maxn] ;
- void reset(){
- for(int i=0;i<=n;i++) to[i].clear();
- M.clear() ;
- tim=0;
- ans = 0 ;
- memset(art,0,sizeof(art)) ;
- memset(dfsn,-1,sizeof(dfsn)) ;
- memset(low,0,sizeof(low)) ;
- }
- void DFS(int u,int p)
- {
- dfsn[u]=low[u]=tim++;
- int ch = 0 ;
- for(int i=0;i<(int)to[u].size();i++)
- {
- int v=to[u][i];
- if(dfsn[v]==-1){
- ch++ ;
- DFS(v,u);
- low[u]=min(low[u],low[v]);
- if(dfsn[u]>0 && low[v]>=dfsn[u]) art[u]=1 ;
- }
- else if(v!=p)low[u]=min(low[u],dfsn[v]);
- }
- if(dfsn[u]==0 && ch>1) art[u]=1 ;
- }
- int main() {
- freopen("C:\\Users\\Mazhar\\Desktop\\Text_Files\\in.txt", "r", stdin);
- string city1,city2 ;
- int ct=0 ;
- while(1){
- scanf("%d",&n) ;
- if(!n) break ;
- if(ct) cout<<endl ;
- reset() ;
- for(int i=0;i<n;i++) {
- cin>>city1 ;
- // M[city1]=i ;
- MM[i]=city1 ;
- }
- sort(MM,MM+n) ;
- for(int i=0;i<n;i++) {
- M[MM[i]]=i ;
- }
- scanf("%d",&e) ;
- while(e--){
- cin>>city1>>city2 ;
- int u = M[city1] ;
- int v = M[city2] ;
- to[u].push_back(v) ;
- to[v].push_back(u) ;
- }
- for(int i=0;i<n;i++){
- if(dfsn[i]==-1) {
- tim = 0 ;
- DFS(i,-1);
- }
- }
- for(int i=0;i<n;i++){
- ans+=art[i] ;
- }
- printf("City map #%d: %d camera(s) found\n",++ct,ans) ;
- for(int i=0;i<n;i++){
- if(art[i]) cout<<MM[i]<<endl ;
- }
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment