# 2115. Find All Possible Recipes from Given Supplies

{%hackmd theme-dark %}

> Input:
> recipes = ["bread", "burger"],
> ingredients = [["yeast","flour"], ["bread", "yeast"]]
> supplies = ["yeast","flour","corn"]
>

Return a list of all the recipes that you can create. You may return the answer in any order.

// ex bread in=0 yeast","flour in supplies
// ex burger in= 1 yeast in sup but bread not yet

class Solution {
public:
    vector<string> findAllRecipes(vector<string>& recipes, vector<vector<string>>& ingredients, vector<string>& supplies) {
        unordered_map<string, unordered_set<string>> graph;
        unordered_map<string, int> indegree;
        unordered_set<string> supply(supplies.begin(), supplies.end());
        
        for (auto &recipe: recipes) {
            indegree[recipe] = 0;
        }
        
        for (int i = 0; i < ingredients.size(); i++) {
            for (auto &ingred: ingredients[i]) {
                if (supply.find(ingred) == supply.end()) {
                    graph[ingred].insert(recipes[i]);
                    indegree[recipe[i]]++;
                }
            }
        }
        // graph[bread]: burger;
        queue<string> q;
        for (auto &[recipe, degree]: indegree) {
            if (degree == 0) {
                q.push(recipe);
            }
        }
        
        vector<string> res;
        // q: bread
        while (!q.emtpy()) {
            auto recipe = q.front();
            q.pop();
            
            res.push_back(recipe);
            for (auto &ingred: graph[recipe]) {
                if (--indegree[ingred] == 0) {
                    q.push(ingred);
                }
            }
        }
        
        return res;
    }
};

###### tags: `mock interview` `面試`