find-all-possible-recipes-from-given-supplies.cpp

// Time:  O(|E|)
// Space: O(|E|)

class Solution {
public:
    vector<string> findAllRecipes(vector<string>& recipes, vector<vector<string>>& ingredients, vector<string>& supplies) {
        unordered_map<string, int> indegree;
        unordered_map<string, vector<string>> adj;
        for (int i = 0; i < size(recipes); ++i) {
            indegree[recipes[i]] = size(ingredients[i]);
            for (const auto& ing : ingredients[i]) {
                adj[ing].emplace_back(recipes[i]);
            }
        }
        vector<string> result;
        unordered_set<string> recipes_set(cbegin(recipes), cend(recipes));
        vector<string> q = supplies;
        while (!empty(q)) { 
            vector<string> new_q;
            for (const auto& u : q) {
                if (recipes_set.count(u)) {
                    result.emplace_back(u);
                }
                for (const auto& v : adj[u]) {
                    if (!--indegree[v]) {
                        new_q.emplace_back(v);
                    }
                }
            }
            q = move(new_q);
        }
        return result ;
    }
};