fork download
  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
stdin
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
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.