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
75
76
77
78
79
80
81

#include <iostream>
#include <cstring>
#include <unordered_map>
#include <vector>
#include <queue>

class Solution {
    std::unordered_map<int, std::string> int_to_str;
    std::unordered_map<std::string, int> str_to_int;
    int cnt = -1;
    
    int insert(const std::string& name) {
        if (str_to_int.count(name)) {
            return str_to_int[name];
        }
        ++cnt;
        int_to_str[cnt] = name;
        str_to_int[name] = cnt;
        return cnt;
    }
    
    int get(const std::string& str) {
        return str_to_int[str];
    }
    
    std::string get(int id) {
        return int_to_str[id];
    }
    
public:
    std::vector<string> findAllRecipes(std::vector<std::string>& recipes, std::vector<std::vector<std::string>>& ingredients, std::vector<std::string>& supplies) {
        std::queue<int> q;
        for (auto& name : supplies) {
            q.push(insert(name));
        }
        for (auto& name : recipes) {
            insert(name);
        }
        for (auto& ingredient : ingredients) {
            for (auto& name : ingredient) {
                insert(name);
            }
        }
        
        int V = cnt + 1;
        std::vector<std::vector<int>> adj(V);
        std::vector<int> isRecipe(V, 0);
        int m = recipes.size();
        for (int i = 0; i < m; ++i) {
            int u = get(recipes[i]);
            isRecipe[u] = true;
            for (auto& name : ingredients[i]) {
                adj[get(name)].push_back(u);
            }
        }
        
        std::vector<int> inDegree(V, 0);
        for (int u = 0; u < V; ++u) {
            for (int v : adj[u]) {
                ++inDegree[v];
            }
        }
        
        std::vector<std::string> res;
        while (!q.empty()) {
            int u = q.front();
            q.pop();
            if (isRecipe[u]) {
                res.push_back(get(u));
            }
            
            for (int v : adj[u]) {
                --inDegree[v];
                if (inDegree[v] == 0) {
                    q.push(v);
                }
            }
        }
        return res;
    }
};