2115. Find All Possible Recipes from Given Supplies

T: O(V+E)
S: O(n*m + m), ingredients: n, recipes: m

class Solution {
    public List<String> findAllRecipes(String[] recipes, List<List<String>> ingredients, String[] supplies) {
        Map<String, List<String>> graph = new HashMap<>();
        Map<String, Integer> indegree = new HashMap<>();
        Set<String> recipesSet = new HashSet<>();
        
        for (int i = 0; i < recipes.length; i++) {
            recipesSet.add(recipes[i]);
            for (int j = 0; j < ingredients.get(i).size(); j++) {
                String from = ingredients.get(i).get(j);
                String to = recipes[i];
                
                graph.putIfAbsent(from, new ArrayList<>());
                graph.get(from).add(to);
                
                indegree.put(to, indegree.getOrDefault(to, 0)+1);
            }
        }
        
        // this question's begin is using supplies
        Queue<String> queue = new LinkedList<>();
        for (String supply : supplies) {
            queue.offer(supply);
        }
        
        List<String> res = new ArrayList<>();
        while (!queue.isEmpty()) {
            String from = queue.poll();
            if (recipesSet.contains(from)) {
                res.add(from);
            }
            for (String to : graph.getOrDefault(from, new ArrayList<>())) {
                indegree.put(to, indegree.get(to) - 1);
                if (indegree.get(to) == 0) {
                    queue.offer(to);
                }
            }
        }
        return res;
    }
}

/*

recipes = ["bread","sandwich"], ingredients = [["yeast","flour"],["bread","meat"]]
supplies = ["yeast","flour","corn"]


"yeast", \bread
"flour" /     \  sandwich
          meat/      
          
supplies = ["yeast","flour","meat"] => indegree = 0


"yeast"   bread   sandwich   burger
"flour"   meat    meat
                  bread
                  
use topology sort:

ingredients: from
recipes: to
supplies: are the begins

T: O(V+E)
S: O(n*m + m), ingredients: n, recipes: m
*/

better one:

class Solution {
    public List<String> findAllRecipes(String[] recipes, List<List<String>> ingredients, String[] supplies) {
        Set<String> recipeSet = new HashSet<>();
        Map<String, Integer> indegree = new HashMap<>();
        Map<String, List<String>> graph = buildGraph(recipes, ingredients, indegree, recipeSet);
        
        Queue<String> queue = new LinkedList<>();
        for (String supply : supplies) {
            queue.offer(supply);
        }
        List<String> result = new ArrayList<>();
        while (!queue.isEmpty()) {
            String cur = queue.poll();
            if (recipeSet.contains(cur)) {
                result.add(cur);
            }
            for (String next : graph.getOrDefault(cur, new ArrayList<>())) {
                indegree.put(next, indegree.getOrDefault(next, 0)-1);
                if (indegree.get(next) == 0) {
                    queue.offer(next);
                }
            }
        }
        return result;
    }
    private Map<String, List<String>> buildGraph(String[] recipes, List<List<String>> ingredients, Map<String, Integer> indegree, Set<String> recipeSet) {
        Map<String, List<String>> graph = new HashMap<>();
        for (int i = 0; i < recipes.length; i++) {
            String to = recipes[i];
            recipeSet.add(to);
            for (String from : ingredients.get(i)) {
                graph.putIfAbsent(from, new ArrayList<>());
                graph.get(from).add(to);
                
                indegree.put(to, indegree.getOrDefault(to, 0) + 1);
            }
        }
        return graph;
    }
}

/*

["yeast","flour"] -> "bread"
                     ["bread","meat"] -> sandwich
           
           s
        "yeast"
         "flour"    -> "bread"  -> sandwich       
                        "meat"
                          s
                          
      bread indree is 2
      sandwich is 2
      
      so when bread, sandwich indegree == 0 -> means we can arrive, 
      and we'll check when something arrive, is it existed in recipes 
      
      T: build graph: ingredients*recipes + supplies + topology sort O(V+E)
                          
*/