fork download
copy 
  1. #include<stdio.h>
  2. #include<string.h>
  3. #include<algorithm>
  4. #include<vector>
  5. #define N 100
  6. #define S_SIZE 40
  7. #define TRIE_SIZE 10000
  8. using namespace std;
  9. struct trie_node{int next[26],no;}trie[TRIE_SIZE];
  10. int visit[N],low[N],n,cnt;
  11. char name[N][S_SIZE],s[S_SIZE];
  12. bool G[N][N];
  13. vector<int>ans;
  14. int getno(int i,int p){
  15.     if(!s[i])return trie[p].no;
  16.     return getno(i+1,trie[p].next[s[i]-97]);
  17. }
  18. void dfs(int p,int i){
  19.     int child=0;
  20.     bool is_av=0;
  21.     visit[i]=low[i]=++cnt;
  22.     for(int j=0;j<n;j++)if(G[i][j]&&j!=p){
  23.         if(visit[j])low[i]=min(low[i],visit[j]);
  24.         else{
  25.             dfs(i,j);
  26.             low[i]=min(low[i],low[j]);
  27.             if(low[j]>=visit[i])is_av=1;
  28.             child++;
  29.         }
  30.     }
  31.     if(i==p&&child>1||i!=p&&is_av)ans.push_back(i);
  32. }
  33. bool ans_cmp(int i,int j){
  34.     return strcmp(name[i],name[j])<0;
  35. }
  36. int main(){
  37.     for(int t=1;scanf("%d",&n)&&n;t++){
  38.         int trie_size=1,m;
  39.         memset(trie,-1,sizeof(trie));
  40.         memset(visit,0,sizeof(visit));
  41.         memset(G,0,sizeof(G));
  42.         ans.clear();
  43.         cnt=0;
  44.         for(int i=0;i<n;i++){
  45.             int p=0;
  46.             scanf("%s",name[i]);
  47.             for(int j=0;name[i][j];j++){
  48.                 if(trie[p].next[name[i][j]-97]==-1)trie[p].next[name[i][j]-97]=trie_size++;
  49.                 p=trie[p].next[name[i][j]-97];
  50.             }
  51.             trie[p].no=i;
  52.         }
  53.         scanf("%d",&m);
  54.         for(int i=0;i<m;i++){
  55.             int a,b;
  56.             scanf("%s",s);
  57.             a=getno(0,0);
  58.             scanf("%s",s);
  59.             b=getno(0,0);
  60.             G[a][b]=G[b][a]=1;
  61.         }
  62.         dfs(0,0);
  63.         sort(ans.begin(),ans.end(),ans_cmp);
  64.         printf("City map #%d: %d camera(s) found\n",t,ans.size());
  65.         for(int i=0;i<ans.size();i++)puts(name[ans[i]]);
  66.         putchar('\n');
  67.     }
  68.     return 0;
  69. }
  70.  
Not running #stdin #stdout 0s 0KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/hZw7Q
language:
C++ (gcc 8.3)
created:
13 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!