uva 11060 - Beverages

Problem E - Beverages

Time Limit: 1 second

Dilbert has just finished college and decided to go out with friends. Dilbert has some strange habits and thus he decided to celebrate this important moment of his life drinking a lot. He will start drinking beverages with low alcohol content, like beer, and then will move to a beverage that contains more alcohol, like wine, until there are no more available beverages. Once Dilbert starts to drink wine he will not drink beer again, so the alcohol content of the beverages never decreases with the time.
You should help Dilbert by indicating an order in which he can drink the beverages in the way he wishes.

Input

Each test case starts with 1 ≤ N ≤ 100, the number of available beverages. Then will follow N lines, informing the name of each beverage, a name has less than 51 characters and has no white spaces. Then there is another line with an integer 0 ≤ M ≤ 200 and M lines in the form B₁ B₂ will follow, indicating that beverage B₂ has more alcohol that beverage B₁, so Dilbert should drink beverage B₁ before he starts drinking beverage B₂. Be sure that this relation is transitive, so if there is also a relation B₂ B₃ you should drink B₁ before you can drink B₃. There is a blank line after each test case. In the case there is no relation between two beverages Dilbert should start drinking the one that appears first in the input. The input is terminated by end of file (EOF).

Output

For each test case you must print the message: Case #C: Dilbert should drink beverages in this order: B₁ B₂ ... B_N., where C is the number of the test case, starting from 1, and B₁ B₂ ... B_N is a list of the beverages such that the alcohol content of beverage B_i+1 is not less than the alcohol content of beverage B_i-1. After each test case you must print a blank line.

Sample Input

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

Sample Output

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.

---

Problem setter: Sérgio Queiroz de Medeiros
Topological sort + priority queue

#include<stdio.h>
#include<cstring>
#include<string>
#include<map>
#include<queue>
#include<vector>
#define REP(i, b, n) for (int i = b; i < n; i++)
#define rep(i,n) REP(i, 0, n)
#define DBG 0
using namespace std;

int N,cnt[100],cases=1;
vector<int>egs[100];
map<string,int>mp;
vector<string>name;
void ans(){
    vector<int>res;
    int top=-1,cur,b;
    priority_queue<pair<int,int> >q;
    rep(i,N){
        if(!cnt[i]){
            if(DBG)printf("cnt[%d]=0\n",i);
            q.push(make_pair(-1*i,i));
        }
    }
    rep(i,N){
        cur=q.top().second,q.pop();
        if(DBG)printf("cur %d\n",cur+1);
        res.push_back(cur);
        rep(j,egs[cur].size()){
            b=egs[cur][j];
            cnt[b]--;
            if(!cnt[b])q.push(make_pair(-1*b,b));
        }
    }
    bool ll=0;
    printf("Case #%d: Dilbert should drink beverages in this order: ",cases++);
    rep(i,res.size()){if(ll)printf(" ");ll=1;printf("%s",name[res[i]].c_str());}
    printf(".\n\n");
}
int main(){
    char chs[100],chs2[100];
    int m,a,b,num;
    while(scanf("%d",&N)==1){
        num=0,name.clear(),mp.clear(),memset(cnt,0,sizeof(cnt));
        rep(i,100)egs[i].clear();
        rep(i,N)scanf("%s",chs),mp[chs]=num++,name.push_back(chs);
        scanf("%d",&m);
        rep(i,m)scanf("%s%s",chs,chs2),a=mp[chs],b=mp[chs2],egs[a].push_back(b),cnt[b]++;
        ans();
    }
}