You have information about n different recipes. You are given a string array recipes and a 2D string array ingredients. The ith recipe has the name recipes[i], and you can create it if you have all the needed ingredients from ingredients[i]. Ingredients to a recipe may need to be created from other recipes, i.e., ingredients[i] may contain a string that is in recipes.

You are also given a string array supplies containing all the ingredients that you initially have, and you have an infinite supply of all of them.

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

Note that two recipes may contain each other in their ingredients.

&nbsp;
Example 1:

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".


Example 2:

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".


Example 3:

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".


&nbsp;
Constraints:


	n == recipes.length == ingredients.length
	1 &lt;= n &lt;= 100
	1 &lt;= ingredients[i].length, supplies.length &lt;= 100
	1 &lt;= recipes[i].length, ingredients[i][j].length, supplies[k].length &lt;= 10
	recipes[i], ingredients[i][j], and supplies[k] consist only of lowercase English letters.
	All the values of recipes and supplies&nbsp;combined are unique.
	Each ingredients[i] does not contain any duplicate values.


class Solution:
	def findAllRecipes(self, recipes: List[str], ingredients: List[List[str]], supplies: List[str]) -> List[str]:

		graph = defaultdict(list)
		in_degree = defaultdict(int)
		for r,ing in zip(recipes,ingredients):
			for i in ing:
				graph[i].append(r)
				in_degree[r]+=1

		queue = supplies[::]
		res = []
		while queue:
			ing = queue.pop(0)
			if ing in recipes:
				res.append(ing)

			for child in graph[ing]:
				in_degree[child]-=1
				if in_degree[child]==0:
					queue.append(child)

		return res
class Solution {
    private static final int NOT_VISITED = 0;
    private static final int VISITING = 1;
    private static final int VISITED = 2;

    public List<String> findAllRecipes(String[] recipes, List<List<String>> ingredients, String[] supplies) {
        Map<String, Integer> status = new HashMap<>();
        Map<String, List<String>> prereqs = new HashMap<>();

        for (int i = 0; i < recipes.length; ++ i) {
            status.put(recipes[i], NOT_VISITED);
            prereqs.put(recipes[i], ingredients.get(i));
        }

        for (String s: supplies) {
            status.put(s, VISITED);
        }

        List<String> output = new ArrayList<>();
        for (String s: recipes) {
            dfs (s, prereqs, status, output);
        }

        return output;
    }

    public boolean dfs(String s, Map<String, List<String>> prereqs, Map<String, Integer> status, List<String> output) {
        if (!status.containsKey(s)) {
            return false;
        }

        if (status.get(s) == VISITING) {
            return false;
        }

        if (status.get(s) == VISITED) {
            return true;
        }

        status.put(s, VISITING);
        for (String p: prereqs.get(s)) {
            if (!dfs(p, prereqs, status, output)) {
                return false;
            }
        }
        status.put(s, VISITED);
        output.add(s);

        return true;
    }
}
class Solution {
public:
    
    // idea is to use TOPOLOGICAL SORTING
    
    // where any foood item with indegree 0 means that item can be created
    
    vector<string> findAllRecipes(vector<string>& recipes, vector<vector<string>>& ingredients, vector<string>& supplies) {
        
        // store what all dependencies exist for any item
        // similar to adjacent list of any node N
        // here node N is string, and all neighbour nodes are stored as vector<string>
        map<string, vector<string>> adjList;
        
        // to keep track of whether item can be made or still needs something before we can make it
        map<string, int>indegree;
        
        // check for each row of 2D matrix
        for(int i=0; i<ingredients.size(); i++)
        {
            // this will list out all the items need to make recipes[i]
            for(auto &item : ingredients[i])
            {
                // 'item' is required to make 'recipes[i]'
                adjList[item].push_back(recipes[i]);
                
                // recipes[i] now has a dependency 
                indegree[recipes[i]]++;
            }
        }
        
        // will contain all items which can be made
        queue<string>q;
        
        // check from the list of given supplies, if some item is independent and we can make it or use it to make others
        for(auto &x : supplies)
            if(indegree[x]==0)
                q.push(x);
        
        
        
        while(!q.empty())
        {
            string node = q.front();
            q.pop();
            
            
            for(auto &nei : adjList[node])
            {
                // remove link of all neighbours of 'node'
                indegree[nei]--;
                
                // if something becomes independent, add it to our queue
                if(indegree[nei]==0)
                    q.push(nei);
            }
        }
        
        
        vector<string> ans;
        
        // all things which have 0 indegree means that they can be made. hence, they will be part of our answer
        for(auto &x : recipes)
            if(indegree[x]==0)
                ans.push_back(x);
            
        return ans;
    }
};
var findAllRecipes = function(recipes, ingredients, supplies) {
    const setOfIngredients = new Set(supplies);
    const recipesWithIngredients = new Map();
    const progress = new Map();
    //map recipes to it's ingredients and set each recipe to false in another map called progress
    for(let i = 0; i < recipes.length; i++) {
        recipesWithIngredients.set(recipes[i], ingredients[i]);
        progress.set(recipes[i], false)
    }

    const result = [];

    for(const rec of recipes) {
        if(recurse(rec, recipesWithIngredients, setOfIngredients, progress)) {
            result.push(rec);
            setOfIngredients.add(rec);
        }
    }

    return result;
};

function recurse(rec, recipesWithIngredients, setOfIngredients, progress) {
    const currentIngredients = recipesWithIngredients.get(rec);
    for(const ingredient of currentIngredients) {
        if(setOfIngredients.has(rec)) continue;
        if(setOfIngredients.has(ingredient)) continue;

        else if(recipesWithIngredients.has(ingredient)) {
            if(progress.get(ingredient)) return false;
            progress.set(ingredient, true);
            let hasCycle = recurse(ingredient, recipesWithIngredients, setOfIngredients, progress);
            if(!hasCycle) return false;
            setOfIngredients.add(ingredient);
        } else {
            return false;
        }
    }
    return true;
}
Find All Possible Recipes from Given Supplies