11060 - Beverages.cpp

#include<bits/stdc++.h>
using namespace std;

vector<int>v[105],order;
vector<int>A;
int deg[105];
bool visited[105];

int n,m;

map<string,int>mp;
map<int,string>ma;

void topsort(){

    int q=0;
    memset(visited,false,sizeof(visited));

    while(q!=n){
        for(int j=0;j<A.size();j++){
            int x = A[j];
            if(deg[x]==0 && visited[x]==false){
                visited[x]=true;
                q++;
                order.push_back(x);
                for(int i=0;i<v[x].size();i++){
                    int xx =v[x][i];
                    deg[xx]--;
                }
                break;
            }
        }
    }




}

int main(){

    int sc=1;
   while(scanf("%d",&n)!=EOF){
        string a,b;
        int k=1;
        for(int i=1;i<=n;i++){
            cin>>a;
            mp[a]=k;
            ma[k]=a;
            A.push_back(k);
            k++;
        }

        cin>>m;

        while(m--){
            cin>>a>>b;
            v[mp[a]].push_back(mp[b]);
            deg[mp[b]]++;
        }

        topsort();

        cout<<"Case #"<<sc<<": Dilbert should drink beverages in this order:";
        for(int i=0;i<order.size();i++){
            cout<<" "<<ma[order[i]];
        }
        cout<<".\n";

        for(int i=0;i<=n;i++){
            v[i].clear();
        }

        order.clear();

        memset(deg,0,sizeof(deg));

        mp.clear();
        ma.clear();
        A.clear();
        sc++;

        cout<<"\n";
   }

}