leetcode-2115：从给定原材料中找到所有可以做出的菜

题目

题目连接

你有 n 道不同菜的信息。给你一个字符串数组 recipes 和一个二维字符串数组 ingredients 。第 i 道菜的名字为 recipes[i] ，如果你有它 所有 的原材料 ingredients[i] ，那么你可以 做出 这道菜。一道菜的原材料可能是 另一道 菜，也就是说 ingredients[i] 可能包含 recipes 中另一个字符串。

同时给你一个字符串数组 supplies ，它包含你初始时拥有的所有原材料，每一种原材料你都有无限多。

请你返回你可以做出的所有菜。你可以以 任意顺序 返回它们。

注意两道菜在它们的原材料中可能互相包含。

示例 1：

输入：recipes = ["bread"], ingredients = [["yeast","flour"]], supplies = ["yeast","flour","corn"]
输出：["bread"]
解释：
我们可以做出 "bread" ，因为我们有原材料 "yeast" 和 "flour" 。

示例 2：

输入：recipes = ["bread","sandwich"], ingredients = [["yeast","flour"],["bread","meat"]], supplies = ["yeast","flour","meat"]
输出：["bread","sandwich"]
解释：
我们可以做出 "bread" ，因为我们有原材料 "yeast" 和 "flour" 。
我们可以做出 "sandwich" ，因为我们有原材料 "meat" 且可以做出原材料 "bread" 。

示例 3：

输入：recipes = ["bread","sandwich","burger"], ingredients = [["yeast","flour"],["bread","meat"],["sandwich","meat","bread"]], supplies = ["yeast","flour","meat"]
输出：["bread","sandwich","burger"]
解释：
我们可以做出 "bread" ，因为我们有原材料 "yeast" 和 "flour" 。
我们可以做出 "sandwich" ，因为我们有原材料 "meat" 且可以做出原材料 "bread" 。
我们可以做出 "burger" ，因为我们有原材料 "meat" 且可以做出原材料 "bread" 和 "sandwich" 。

示例 4：

输入：recipes = ["bread"], ingredients = [["yeast","flour"]], supplies = ["yeast"]
输出：[]
解释：
我们没法做出任何菜，因为我们只有原材料 "yeast" 。

解题

方法一：暴力模拟

以现有的原料制作，把新做出来的菜，也添加到原料中，反复循环直到没有新的菜增加，就返回结果

class Solution {
    
public:
    vector<string> findAllRecipes(vector<string>& recipes, vector<vector<string>>& ingredients, vector<string>& supplies) {
    
        vector<string> res;
        unordered_set<string> set;
        for(string& s:supplies){
    //记录现有的原材料
            set.insert(s);
        }

        int preLen;//当前所有原材料的长度
        while(true){
    
            int preLen=set.size();
            for(int i=0;i<recipes.size();i++){
    
                if(set.count(recipes[i])) continue;
                vector<string> tmp=ingredients[i];
                bool ok=true;//如果为true说明可以做这道菜
                for(int j=0;j<tmp.size();j++){
    
                    if(!set.count(tmp[j])){
    
                        ok=false;
                        break;
                    }
                }
                if(ok){
    //如果本这次菜品可以做
                    set.insert(recipes[i]);//本次菜品添加为原材料
                    res.push_back(recipes[i]);//保存结果
                }
            }
            if(set.size()<=preLen) break;//如果原材料不再增加了，说明剩下的菜品都没法制作了
        }
        return res;

    }
};

方法二：拓扑排序

从原材料出发，当菜品对应的入度为0的时候，说明原材料齐全，把菜品再加入到原材料中。
得到入度为0的点，就是可以做的菜品。

class Solution {
    
public:
    vector<string> findAllRecipes(vector<string>& recipes, vector<vector<string>>& ingredients, vector<string>& supplies) {
    
        unordered_map<string,vector<string>> graph;
        unordered_map<string,int> indeg;
        int n=recipes.size();
        for(int i=0;i<n;i++){
    
            for(int j=0;j<ingredients[i].size();j++){
    
                graph[ingredients[i][j]].push_back(recipes[i]);
                indeg[recipes[i]]++;
            }
        }
        queue<string> q;
        for(string& s:supplies){
    
            q.push(s);
        }

        vector<string> res;
        while(!q.empty()){
    
            string x=q.front();
            q.pop();
            for(string& y:graph[x]){
    
                if(--indeg[y]==0){
    
                    q.push(y);
                    res.push_back(y);
                }
            }
            
        }
        return res;
    }
};