---
title: 2115. Find All Possible Recipes from Given Supplies
tags: graph
description: share source code.
---

# 2115. Find All Possible Recipes from Given Supplies

class Solution {
    public List<String> findAllRecipes(String[] recipes, List<List<String>> ingredients, String[] supplies) {
//            Set<String> supplyList = Arrays.stream(supplies).collect(Collectors.toSet());
//            for(String supply : supplies){
//                supplyList.add(supply);
//            }
        
           List<String> ans = new ArrayList<>();
        
           Map<String, List<String>> graph = new HashMap<>();
           Map<String, Integer> indegrees = new HashMap<>();
        
           for(int i = 0; i < recipes.length; i++){
               for(String cur_ingredient : ingredients.get(i)){
                  // if(supplyList.contains(cur_ingredient)){
                       graph.putIfAbsent(cur_ingredient, new ArrayList<>());
                       graph.get(cur_ingredient).add(recipes[i]);
                       indegrees.put(recipes[i], indegrees.getOrDefault(recipes[i], 0) + 1);
                 //  }
               }
           }
        
//         System.out.println("key: " + graph.keySet().toString());
//         System.out.println("val: " + graph.values().toString());
        
           //int INF = Integer.MAX_VALUE/2;
        
           Queue<String> q = new LinkedList<>();
           for(String supply : supplies){
                // indegrees.put(supply, INF);
                q.offer(supply);
           }
           
           while(!q.isEmpty()){
               String u = q.poll();
               
               if(!graph.containsKey(u)){
                   continue;
               }
               
               for(String v:  graph.get(u)){
             
                   indegrees.put(v, indegrees.get(v) - 1);
                   if( indegrees.get(v) == 0){
                       ans.add(v);
                       q.offer(v);
                   }
               }
           }
        
          return ans;
           
    }
}