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

拓扑排序

题面

题目链接：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;
    }
};