fork(3) download
  1. #include<iostream>
  2. #include<map>
  3. #include<string>
  4. #include<algorithm>
  5. #include<stack>
  6. #include<vector>
  7. #include<string.h>
  8. using namespace std;
  9. int n,z,M[102][102],List[102];
  10. bool vis[102];
  11. vector<int>G[102];
  12. map<string,int>s2i;
  13. map<int,string>i2s;
  14. stack<int>order;
  15. void dfs(int s);
  16. void top_sort()
  17. {
  18. for(int i=0;i<n;i++)
  19. {
  20. if(vis[i]==false)
  21. {
  22. dfs(i);
  23. }
  24. }
  25. }
  26. void dfs(int s)
  27. {
  28. for(int i=0;i<G[s].size();i++)
  29. {
  30. if(vis[G[s][i]]==false)
  31. {
  32. dfs(G[s][i]);
  33. }
  34. }
  35. vis[s]=true;
  36. List[z--]=s;
  37. }
  38. int check(string s1,string s2)
  39. {
  40. int f=0;
  41. int x=s2i[s1];
  42. int y=s2i[s2];
  43. for(int i=0;i<G[x].size();i++)
  44. {
  45. if(G[x][i]==y)
  46. {
  47. f=1;
  48. break;
  49. }
  50. }
  51. return f;
  52. }
  53. void Sort()
  54. {
  55. int i,j;
  56. for(i=1;i<n;i++)
  57. {
  58. for(j=i;j>0;j--)
  59. {
  60. if(!M[List[j-1]][List[j]])
  61. {
  62. if(List[j-1]>List[j])
  63. {
  64. swap(List[j],List[j-1]);
  65.  
  66. }
  67.  
  68. }
  69.  
  70. }
  71. }
  72. }
  73. int main()
  74. {
  75. int i,k,m,t=0;
  76. string s1,s2;
  77. while(cin>>n)
  78. {
  79. z=n-1;
  80. //if(t)
  81. // cout<<endl;
  82. for(i=0,k=0;i<n;i++)
  83. {
  84. cin>>s1;
  85. i2s[k]=s1;
  86. s2i[s1]=k++;
  87. }
  88. cin>>m;
  89. while(m--)
  90. {
  91. cin>>s1>>s2;
  92. G[s2i[s1]].push_back(s2i[s2]);
  93. M[s2i[s1]][s2i[s2]]=1;
  94. }
  95. cout<<"Case #"<<++t<<": Dilbert should drink beverages in this order:";
  96. top_sort();
  97. Sort();
  98. for(i=0;i<n;i++)
  99. cout<<" "<<i2s[List[i]];
  100. cout<<"."<<endl<<endl;
  101. s2i.clear();
  102. i2s.clear();
  103. for(i=0;i<n;i++)
  104. {
  105. G[i].clear();
  106. vis[i]=false;
  107. }
  108. memset(M,0,sizeof(M));
  109. }
  110. return 0;
  111. }
  112.  
Success #stdin #stdout 0s 3528KB
stdin
3
vodka
wine
beer
2
wine vodka
beer wine

5
wine
beer
rum
apple-juice
cachaca
6
beer cachaca
apple-juice beer
apple-juice rum
beer rum
beer wine
wine cachaca

10
cachaca
rum
apple-juice
tequila
whiskey
wine
vodka
beer
martini
gin
11
beer whiskey
apple-juice gin
rum cachaca
vodka tequila
apple-juice martini
rum gin
wine whiskey
apple-juice beer
beer rum
wine vodka
beer tequila
stdout
Case #1: Dilbert should drink beverages in this order: beer wine vodka.

Case #2: Dilbert should drink beverages in this order: apple-juice beer wine rum cachaca.

Case #3: Dilbert should drink beverages in this order: apple-juice wine vodka beer rum cachaca tequila whiskey martini gin.