5947. 从给定原材料中找到所有可以做出的菜

目录

• • 1. 题意
  • 2. 算法
  • 3. 思路
  • • 代码

1. 题意

给定 一维数组 recipes 表示菜谱，二维数组 ingredients 每道菜的原材料， 一维数组 supplies 提供的材料，找出能做出的所有菜。

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

---

2. 算法

哈希表 + 拓扑排序

---

3. 思路

1. 建图。用hash存储，对于给定的菜谱，我们可以建边，从这道菜的原材料向这道菜连边，而菜谱入度++。
2. topsort。 先将已有的原材料入队。在图中跑一遍拓排，原材料连向的点入度- -，那么，对于每道菜，如果入度为 0 则表明可以做成，并且当作已有原材料入队，入答案数组。
3. 具体细节，见代码注释~~

---

代码

class Solution {
public:
    vector<string> findAllRecipes(vector<string>& recipes, vector<vector<string>>& ingredients, vector<string>& supplies) {
        int n = recipes.size();
        unordered_map<string, vector<string>> mp; // 图
        unordered_map<string, int> d;  // 入度
        for (int i = 0; i < n; i++) {
            for (auto &x: ingredients[i]) {
                // 原材料能提供的菜
                mp[x].push_back(recipes[i]);
            }
            // 菜入度 = 其原材料个数
            d[recipes[i]] = ingredients[i].size();
        }

        vector<string> ans; // 答案数组
        queue<string> q; // 队列
        // 初始材料入队
        for (auto &x : supplies) {
            q.push(x);
        }

        // topsort
        while(!q.empty()) {
            auto x = q.front();
            q.pop();
            if(mp.count(x)) {
                for (auto &y : mp[x]) {
                    // 入度为0， 说明能做出这道菜
                    if(--d[y] == 0) {
                        ans.push_back(y);
                        q.push(y);
                    }
                }
            }
        }
        return ans;

    }
};