Find All Possible Recipes from Given Supplies

lcpy gen -n 2115   # by problem number
lcpy gen -s find_all_possible_recipes_from_given_supplies   # by problem name

Input: recipes = ["bread"], ingredients = [["yeast","flour"]], supplies = ["yeast","flour","corn"]
Output: ["bread"]
Explanation:
We can create "bread" since we have the ingredients "yeast" and "flour".

Input: recipes = ["bread","sandwich"], ingredients = [["yeast","flour"],["bread","meat"]], supplies = ["yeast","flour","meat"]
Output: ["bread","sandwich"]
Explanation:
We can create "bread" since we have the ingredients "yeast" and "flour".
We can create "sandwich" since we have the ingredient "meat" and can create the ingredient "bread".

Input: recipes = ["bread","sandwich","burger"], ingredients = [["yeast","flour"],["bread","meat"],["sandwich","meat","bread"]], supplies = ["yeast","flour","meat"]
Output: ["bread","sandwich","burger"]
Explanation:
We can create "bread" since we have the ingredients "yeast" and "flour".
We can create "sandwich" since we have the ingredient "meat" and can create the ingredient "bread".
We can create "burger" since we have the ingredient "meat" and can create the ingredients "bread" and "sandwich".

from collections import deque


class Solution:
    # Time: O(V + E) over recipes and ingredient references
    # Space: O(V + E)
    def find_all_recipes(
        self, recipes: list[str], ingredients: list[list[str]], supplies: list[str]
    ) -> list[str]:
        recipe_set = set(recipes)
        remaining = {r: len(ings) for r, ings in zip(recipes, ingredients, strict=True)}
        dependents: dict[str, list[str]] = {}
        for recipe, ings in zip(recipes, ingredients, strict=True):
            for ing in ings:
                dependents.setdefault(ing, []).append(recipe)
        made: list[str] = []
        queue: deque[str] = deque(supplies)
        queue.extend(recipe for recipe in recipes if remaining[recipe] == 0)
        while queue:
            item = queue.popleft()
            if item in recipe_set:
                made.append(item)
            for recipe in dependents.get(item, ()):
                remaining[recipe] -= 1
                if remaining[recipe] == 0:
                    queue.append(recipe)
        return made