All problems

Recipe Production

Medium · topological sort

A kitchen has a shelf of base supplies, each a name such as "flour". Supplies are never used up, so every one can be used as often as needed.

You are also given recipes and ingredients. The recipe recipes[i] can be cooked when every name in ingredients[i] is either a supply or another recipe that can itself be cooked. A cooked recipe is never used up either.

Some ingredients may be neither a supply nor a recipe, and some recipes may depend on each other in a circle. Such recipes can never be cooked.

Return the names of all recipes that can be cooked, in the same order as they appear in recipes. Return an empty list if there are none.

Examples

Example 1

Input: supplies = ["flour", "water", "salt"], recipes = ["bread", "dough"], ingredients = [["dough", "salt"], ["flour", "water"]]

Output: ["bread", "dough"]

Dough needs only supplies. Bread needs dough and salt, so it can be cooked once dough can. The answer follows the order of recipes, not the order of cooking.

Example 2

Input: supplies = ["milk", "sugar"], recipes = ["custard", "caramel", "toffee"], ingredients = [["milk", "egg", "sugar"], ["sugar"], ["caramel", "butter"]]

Output: ["caramel"]

Custard needs egg and toffee needs butter, and neither is a supply or a recipe. Only caramel can be cooked.

Example 3

Input: supplies = ["salt"], recipes = ["chicken", "egg"], ingredients = [["egg", "salt"], ["chicken", "salt"]]

Output: []

Each of the two recipes needs the other one first, so neither can ever be cooked.

Constraints

• 1 <= len(recipes) <= 1000 and len(recipes) == len(ingredients)
• 0 <= len(supplies) <= 1000
• 1 <= len(ingredients[i]) <= 10
• Every name has 1 to 12 characters, each a lower-case letter or a digit.
• Recipe names are all different, and no recipe name is also a supply. Supplies may repeat, and an ingredient list may repeat a name.