2115. 从给定原材料中找到所有可以做出的菜
文章目录
- 题意
- 思路
- 代码
题意
题目链接
原材料和每道菜需要什么材料，能做那些菜
思路
- 拓扑排序
- 暴力
代码
// 暴力
class Solution {
public:vector<string> findAllRecipes(vector<string>& recipes, vector<vector<string>>& ingredients, vector<string>& supplies) {set<string> visit;for (auto &it:supplies)visit.insert(it);vector<string> ans;bool add = true;vector<bool> hash(recipes.size(), false);while (add){add = false;for (int i = 0; i < ingredients.size(); i++){if (hash[i])continue;bool flag = true;for (auto &it:ingredients[i])if (visit.find(it) == visit.end()){flag = false;break;}if (flag){hash[i] = true;visit.insert(recipes[i]);ans.push_back(recipes[i]);add = true;}}}return ans;}
};