competitive-programming/solved-uva/11060.cpp at master · the-redback/competitive-programming · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
/**
 *                                   ____
 *       ____ ___  ____ ________  __/ __/
 *      / __ `__ \/ __ `/ ___/ / / / /_
 *     / / / / / / /_/ / /  / /_/ / __/
 *    /_/ /_/ /_/\__,_/_/   \__,_/_/
 *
 *    @link : https://the-redback.com
 */
#include <bits/stdc++.h>
using namespace std;

#define mem(a, b) memset(a, b, sizeof(a))
#define pb        push_back
#define pp        pop_back
#define inf       10000000
#define NN        5000

map<string, int> mp;
vector<int> e[NN + 7];
vector<int> v;
vector<string> ans;
int pr[NN + 7];
string s, ss;
char a[100], b[100];

void topological(int n) {
    int i, j, k, l, in;
    while (v.size() < n) {
        int mn = inf;
        for (i = 0; i < n; i++)
            if (mn > pr[i]) mn = pr[i], in = i;
        pr[in] = inf;
        v.pb(in);
        for (i = 0; i < e[in].size(); i++) pr[e[in][i]]--;
    }
}

int main() {
    int tc, t = 1;
    int i, j, k, l, m, n, count;
    // scanf("%d",&tc);
    while (~scanf("%d", &n)) {
        for (i = 0; i < n; i++) {
            scanf("%s", &a);
            s.assign(a);
            mp[s] = i;
            ans.pb(s);
            pr[i] = 0;
        }
        scanf("%d", &m);
        while (m--) {
            scanf("%s%s", &a, &b);
            s.assign(a);
            ss.assign(b);
            pr[mp[ss]]++;
            e[mp[s]].pb(mp[ss]);
        }
        topological(n);
        printf("Case #%d: Dilbert should drink beverages in this order:", t++);
        for (i = 0; i < n; i++) {
            printf(" %s", ans[v[i]].c_str());
            e[i].clear();
        }
        printf(".\n\n");
        mp.clear();
        v.clear();
        ans.clear();
    }
    return 0;
}