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
72
73
74
|
#include <string>
#include <unordered_map>
#include <vector>
#ifdef LOCAL
#include "stloutput.h"
#endif
#define INF 1000000000
using namespace std;
bool (int x, vector<int> &path, vector<vector<int>> &g, vector<int> &ref,
int N) {
if (path.size() == N) return true;
for (int i = 0; i < N; i++) {
if (g[x][i]) ref[i]--;
}
for (int i = 0; i < N; i++) {
if (ref[i] == 0) {
path.push_back(i);
ref[i]--;
if (dfs(i, path, g, ref, N)) return true;
ref[i]++;
path.pop_back();
}
}
for (int i = 0; i < N; i++) {
if (g[x][i]) ref[i]++;
}
return false;
}
int main() {
int N, kase = 1;
while (cin >> N) {
vector<string> vs;
unordered_map<string, int> um;
vector<vector<int>> graph(N, vector<int>(N));
vector<int> ref(N);
for (int i = 0; i < N; i++) {
string s;
cin >> s;
um[s] = i;
vs.push_back(s);
}
int M;
cin >> M;
for (int i = 0; i < M; i++) {
string a, b;
cin >> a >> b;
if (!graph[um[a]][um[b]]) {
graph[um[a]][um[b]] = 1;
ref[um[b]]++;
}
}
vector<int> path;
for (int i = 0; i < N; i++) {
if (ref[i] == 0) {
ref[i]--;
path.push_back(i);
dfs(i, path, graph, ref, N);
break;
}
}
cout << "Case #" << kase++
<< ": Dilbert should drink beverages in this order:";
for (auto i : path) {
cout << " " << vs[i];
}
cout << '.' << endl << endl;
}
}
|
近期评论