Description

Submission

class Solution {
public:
    vector<string> findAllRecipes(vector<string>& recipes, vector<vector<string>>& ingredients, vector<string>& supplies) {
        unordered_set<string> mapRecipes{recipes.begin(), recipes.end()};
        unordered_set<string> mapSupplies{supplies.begin(), supplies.end()};

        int n = recipes.size();
        unordered_map<string, vector<string>> graph;  // from child to parent
        unordered_map<string, int> inDegree;

        for(int i = 0; i < n; ++i) {
            for(auto& ingredient: ingredients[i]) {
                graph[ingredient].push_back(recipes[i]);
                ++inDegree[recipes[i]];
                if(inDegree.find(ingredient) == inDegree.end()) inDegree[ingredient] = 0;
            }
        }

        queue<string> q;
        for(auto& [key, val]: inDegree) {
            if(val == 0 && mapSupplies.find(key) != mapSupplies.end()) q.push(key);
        }
        
        vector<string> rets;
        while(!q.empty()) {
            string cur = q.front();
            q.pop();

            if(mapRecipes.find(cur) != mapRecipes.end())  {
                rets.push_back(cur);
            }

            for(auto& parent: graph[cur]) {
                --inDegree[parent];
                if(inDegree[parent] == 0) q.push(parent);
            }
        }
        
        return rets;
    }
};