fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. #define MAX 100+10
  4. map<int,string>ms;
  5. map<string,int>sm;
  6. vector<int>edgelist[MAX];
  7. string s;
  8. int n,i,m;
  9. int main(){
  10.     //freopen("in.txt","r",stdin);
  11.     //freopen("out.txt","w",stdout);
  12.     int cases=0;
  13.     while(scanf("%d",&n)!=EOF){
  14.         for(i=1;i<=n;i++){
  15.             cin>>s;
  16.             ms[i]=s;
  17.             sm[s]=i;
  18.         }
  19.         scanf("%d",&m);
  20.         vector<int>in(n+1,0);
  21.         for(i=1;i<=m;i++){
  22.             string s1,s2;
  23.             cin>>s1;
  24.             cin>>s2;
  25.             edgelist[sm[s1]].push_back(sm[s2]);
  26.             in[sm[s2]]++;
  27.         }
  28.         /*for(i=1;i<=n;i++){
  29.             for(int j=0;j<edgelist[i].size();j++)in[edgelist[i][j]]++;
  30.         }*/
  31.         //for(i=1;i<=n;i++)cout<<ms[i]<<" : "<<in[i]<<endl;
  32.         queue<int>q;
  33.         for(i=1;i<=n;i++){
  34.             if(in[i]==0)q.push(i);
  35.         }
  36.         vector<int>top_sort;
  37.         while(!q.empty()){
  38.             int u=q.front();
  39.             q.pop();
  40.             top_sort.push_back(u);
  41.             for(i=0;i<edgelist[u].size();i++){
  42.                 int v=edgelist[u][i];
  43.                 --in[v];
  44.                 if(in[v]==0)q.push(v);
  45.             }
  46.         }
  47.         printf("Case #%d: Dilbert should drink beverages in this order: ",++cases);
  48.         //sort(top_sort.begin(),top_sort.end());
  49.         for(i=0;i<top_sort.size();i++){
  50.             cout<<ms[top_sort[i]];
  51.             if(i!=top_sort.size()-1)cout<<" ";
  52.         }
  53.         printf(".\n\n");
  54.         for(i=1;i<=n;i++)edgelist[i].clear();
  55.         ms.clear(),sm.clear();
  56.     }
  57.     return 0;
  58. }
  59.  
Success #stdin #stdout 0s 3468KB
comments (?)
stdin
copy 
8
a
b
c
d
e
f
s
t
6
a e
a b
c d
e f
s t
a t

8
s
a
b
e
f
c
d
t
6
a e
a b
c d
e f
s t
a t

8
a
b
c
s
t
e
f
d
6
a b
a e
c d
e f
s t
a t
stdout
copy 
Case #1: Dilbert should drink beverages in this order: a c s e b d t f.

Case #2: Dilbert should drink beverages in this order: s a c e b t d f.

Case #3: Dilbert should drink beverages in this order: a c s b e d t f.
https://ideone.com/EVHehC
language:
C++14 (gcc 8.3)
created:
7 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!