[UVa] 11060 Beverages.cpp

#include <iostream>
#include <string>
#include <map>
#include <vector>
using namespace std;

map<string, int> Map;
string Name[105];
vector<int> toNxt[105];
int beConnected[105];   //該node被其他點連入的數量

void Initial(int N)
{
    Map.clear();
    for (int i = 0; i < N; ++i) {
        toNxt[i].clear();
        beConnected[i] = 0;
    }
}
int main()
{
  //  freopen("input.txt","rt",stdin);
    ios::sync_with_stdio(false);
    int N, M, Case = 1;
    string s1, s2;
    while (cin >> N) {
        Initial(N);
        for (int i = 0; i < N; ++i)
            cin >> s1, Map[s1] = i, Name[i] = s1;

        cin >> M;
        for (int i = 0; i < M; ++i) {
            cin >> s1 >> s2;
            toNxt[Map[s1]].push_back(Map[s2]);
            ++beConnected[Map[s2]];
        }
        cout << "Case #" << Case++ << ": Dilbert should drink beverages in this order:";
        for (int i = 0; i < N; ++i) {
            int pos = 0;
            while (beConnected[pos] != 0) ++pos;

            beConnected[pos] = -1;
            cout << ' ' << Name[pos];

            for (int nxt : toNxt[pos])
                --beConnected[nxt];
        }
        cout << '.' << endl << endl;
    }
}