UVa - 11060 - Beverages

Problem Link: 11060 - Beverages

#include <bits/stdc++.h>


#define S 103


using namespace std;


 


vector <int> Order[S];


queue <int> ans;


map <string, int> Bev;


map <int, string> Ans;


int cn, indegree[S];


 


int main(){


    string Beverages, x, y;


    int n, m, cs = 0;


    while(cin >> n){


        for(int i = 1; i <= n; i++){


            cin >> Beverages;


            Bev[Beverages] = i;


            Ans[i] = Beverages;


        }


        memset(indegree, 0, sizeof(indegree));


        cin >> m;


        for(int i = 0; i < m; i++){


            cin >> x >> y;


            Order[Bev[x]].push_back(Bev[y]);


            indegree[Bev[y]]++;


        }


        bool f = true;


        while(f){


            int cn = 0;


            for(int i = 1; i <= n; i++){


                if(!indegree[i]){


                    indegree[i] = -1;


                    ans.push(i);


                    int sz = Order[i].size();


                    for(int z = 0; z < sz; z++)indegree[Order[i][z]]--;


                    break;


                }


                cn++;


            }


            if(cn == n)break;


        }


        cout << "Case #" << ++cs << ": Dilbert should drink beverages in this order:";


        while(!ans.empty()){


            cout << " " << Ans[ans.front()];


            ans.pop();


        }


        puts(".");


        puts("");


        Ans.clear(), Bev.clear();


        for(int i = 0; i <= n; i++)Order[i].clear();


    }


    return 0;


}