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; } };
