# 2115. Find All Possible Recipes from Given Supplies
Link: https://leetcode.com/problems/find-all-possible-recipes-from-given-supplies/
###### tags: `Leetcode` `Medium` `Topological Sort`
## 思路
和[0207. Course Schedule](https://hackmd.io/0ggCf_t9R8G8kcJJ8wJkIw) [0210. Course Schedule II](https://hackmd.io/EzKnR3KLQayEp_SAYuXaYQ)类似
Topogical sort
bfs
建立从order低(ingredients, low level courses)到order高(recipes, high level courses)的map
记录每个high level需要多少low level才能被满足，如果减到0，就加到ans
## Code

class Solution {
    public List<String> findAllRecipes(String[] recipes, List<List<String>> ingredients, String[] supplies) {
        Map<String, List<String>> ingredToRec = new HashMap<String, List<String>>();
        Map<String, Integer> needNum = new HashMap<String, Integer>();
        for(int i = 0;i < recipes.length;i++){
            needNum.put(recipes[i], ingredients.get(i).size());
        }
        for(int i = 0;i < ingredients.size();i++){
            for(String ingredient:ingredients.get(i)){
                if(ingredToRec.get(ingredient)==null){
                    ingredToRec.put(ingredient, new ArrayList<String>());
                }
                ingredToRec.get(ingredient).add(recipes[i]);
            }
        }
        
        Queue<String> q = new LinkedList<>();
        List<String> ans = new ArrayList<>();
        for(String supply:supplies){
            q.add(supply);
        }
        while(!q.isEmpty()){
            String s = q.poll();
            List<String> recipeList = ingredToRec.getOrDefault(s, new ArrayList<String>());
            for(String recipe:recipeList){
                needNum.put(recipe, needNum.get(recipe)-1);
                if(needNum.get(recipe)==0){
                    q.add(recipe);
                    ans.add(recipe);
                }
            }
        }
        return ans;
    }
}