拓扑排序
题面
题目链接：2115. 从给定原材料中找到所有可以做出的菜 - 力扣（LeetCode）
你有
n道不同菜的信息。给你一个字符串数组recipes和一个二维字符串数组ingredients。第i道菜的名字为recipes[i]，如果你有它 所有 的原材料ingredients[i]，那么你可以 做出 这道菜。一道菜的原材料可能是 另一道 菜，也就是说ingredients[i]可能包含recipes中另一个字符串。同时给你一个字符串数组
supplies，它包含你初始时拥有的所有原材料，每一种原材料你都有无限多。请你返回你可以做出的所有菜。你可以以 任意顺序 返回它们。
注意两道菜在它们的原材料中可能互相包含。
解题思路
做出一个菜，可以由这个菜作为原料做出另一个，且原料无限
很容易幻想出一个有向图，从原料指向各个目标菜，而拥有公共原料，且之间存在互相作为原料的情况则可以看作图的后序
了解过或者学习过拓扑排序的，到这里应该就能判断谁作为队列的初始元素了
但是题目给出的是原料有哪些，需要做的菜有哪些，它们又各自需要哪些作为原料
所以我们需要用哈希表存储这些关系，避免大量重复的遍历寻找
哈希表1：一个原料能做出哪些菜
哈希表2：一个菜的入度为几（因为每个元素都为string类型，所以也是需要用哈希表）
拓扑排序套路写法
class Solution {
public:vector<string> findAllRecipes(vector<string>& recipes,vector<vector<string>>& ingredients,vector<string>& supplies) {unordered_map<string, int> indegree;unordered_map<string, vector<string>> out;queue<string> q;vector<string> ans;for (string i : supplies)q.push(i);for (int i = 0; i < recipes.size(); i++) {indegree[recipes[i]] = ingredients[i].size();for(string var:ingredients[i]){out[var].push_back(recipes[i]);}}while (!q.empty()) {string now = q.front();q.pop();for(string aim:out[now]){if(--indegree[aim]==0){ans.push_back(aim);q.push(aim);}}}return ans;}
};
