深圳做网站案例网站关键词公司

思路：拓补排序，哈希表

在思路上其实很好发现，我们需要有一个明确的做菜顺序，也就是说需要定下来我们根据原材料先做哪些菜，然后做完该做的菜之后，后来又能做哪些菜。

你也发现了，这个顺序其实就是拓补排序的顺序，我们构造出来这样的一个图就行了，虽然说处理起来很麻烦....需要用到哈希表进行映射才行。

这里哈希表用了两个，一个是用来构建拓补排序的图的，一个是用来存储入度的，因为我们需要判断哪个可以先开始制作。

OK，构造出来做菜的顺序了，也与处理完了入度，我们首先开始下手的肯定是原材料，因为原材料肯定入度为0，这是题目中推出的信息，只有菜谱上的菜之间才可能会有入度。

在处理完原材料之后，减去对应的入度之后，我们开始判断食谱。

注意，食谱这里你需要经过多次循环才能说得出结果，根据数据范围定义循环的次数，因为我们在每一次遍历完数组之后，可能会有原先入度不是0但是遍历完之后入度为0的情况出现，所以这里需要多次对于数组进行遍历。

class Solution {
public:vector<string> findAllRecipes(vector<string>& recipes, vector<vector<string>>& ingredients, vector<string>& supplies) {map<string,int>m;map<string,vector<string>>s;for(int i=0;i<recipes.size();i++)m[recipes[i]]=0;for(int i=0;i<ingredients.size();i++){for(int j =0;j<ingredients[i].size();j++){m[ingredients[i][j]]=0;}}for(int i=0;i<recipes.size();i++){for(int j=0;j<ingredients[i].size();j++){s[ingredients[i][j]].push_back(recipes[i]);}m[recipes[i]]+=ingredients[i].size();}vector<string>res;for(int i=0;i<supplies.size();i++){if(m[supplies[i]]==0){for(int j=0;j<s[supplies[i]].size();j++){m[s[supplies[i]][j]]--;}}}vector<bool>st(recipes.size(),false);int i=0;int n=1e5;while(n--){if(m[recipes[i]]==0&&!st[i]){res.push_back(recipes[i]);st[i]=true;for(int j=0;j<s[recipes[i]].size();j++){m[s[recipes[i]][j]]--;}}i=(i+1)%recipes.size();}return res;}
};

上代码：