Find All Possible Recipes from Given Supplies

class Solution {
public:
    vector<string> findAllRecipes(vector<string>& recipes, vector<vector<string>>& ingredients, vector<string>& supplies) {
        unordered_map<string, vector<string>> adj;
        unordered_map<string, int> indeg;
        unordered_set<string> recipeSet(recipes.begin(), recipes.end());
        for (int i = 0; i < (int)recipes.size(); ++i) {
            indeg[recipes[i]] = ingredients[i].size();
            for (auto& ing : ingredients[i]) adj[ing].push_back(recipes[i]);
        }
        queue<string> q;
        for (auto& s : supplies) q.push(s);
        vector<string> out;
        while (!q.empty()) {
            string u = q.front(); q.pop();
            for (auto& v : adj[u]) {
                if (--indeg[v] == 0) {
                    out.push_back(v);
                    q.push(v);
                }
            }
        }
        return out;
    }
};

func findAllRecipes(recipes []string, ingredients [][]string, supplies []string) []string {
    adj := map[string][]string{}
    indeg := map[string]int{}
    recipeSet := map[string]bool{}
    for _, r := range recipes {
        recipeSet[r] = true
    }
    for i, r := range recipes {
        indeg[r] = len(ingredients[i])
        for _, ing := range ingredients[i] {
            adj[ing] = append(adj[ing], r)
        }
    }
    q := append([]string{}, supplies...)
    out := []string{}
    for len(q) > 0 {
        u := q[0]
        q = q[1:]
        for _, v := range adj[u] {
            indeg[v]--
            if indeg[v] == 0 {
                out = append(out, v)
                q = append(q, v)
            }
        }
    }
    return out
}

from collections import defaultdict, deque
from typing import List

class Solution:
    def findAllRecipes(self, recipes: List[str], ingredients: List[List[str]],
                       supplies: List[str]) -> List[str]:
        adj = defaultdict(list)
        indeg: dict = {}
        recipe_set = set(recipes)
        for r, ings in zip(recipes, ingredients):
            indeg[r] = len(ings)
            for ing in ings:
                adj[ing].append(r)
        q = deque(supplies)
        out: List[str] = []
        while q:
            u = q.popleft()
            for v in adj[u]:
                indeg[v] -= 1
                if indeg[v] == 0:
                    out.append(v)
                    q.append(v)
        return out

function findAllRecipes(recipes, ingredients, supplies) {
    const adj = new Map();
    const indeg = new Map();
    for (let i = 0; i < recipes.length; i++) {
        indeg.set(recipes[i], ingredients[i].length);
        for (const ing of ingredients[i]) {
            if (!adj.has(ing)) adj.set(ing, []);
            adj.get(ing).push(recipes[i]);
        }
    }
    const q = [...supplies];
    const out = [];
    while (q.length > 0) {
        const u = q.shift();
        const neighbors = adj.get(u);
        if (!neighbors) continue;
        for (const v of neighbors) {
            indeg.set(v, indeg.get(v) - 1);
            if (indeg.get(v) === 0) {
                out.push(v);
                q.push(v);
            }
        }
    }
    return out;
}

class Solution {
    public List<String> findAllRecipes(String[] recipes, List<List<String>> ingredients, String[] supplies) {
        Map<String, List<String>> adj = new HashMap<>();
        Map<String, Integer> indeg = new HashMap<>();
        for (int i = 0; i < recipes.length; i++) {
            indeg.put(recipes[i], ingredients.get(i).size());
            for (String ing : ingredients.get(i)) {
                adj.computeIfAbsent(ing, k -> new ArrayList<>()).add(recipes[i]);
            }
        }
        Deque<String> q = new ArrayDeque<>();
        for (String s : supplies) q.offer(s);
        List<String> out = new ArrayList<>();
        while (!q.isEmpty()) {
            String u = q.poll();
            List<String> neighbors = adj.get(u);
            if (neighbors == null) continue;
            for (String v : neighbors) {
                indeg.put(v, indeg.get(v) - 1);
                if (indeg.get(v) == 0) {
                    out.add(v);
                    q.offer(v);
                }
            }
        }
        return out;
    }
}

function findAllRecipes(recipes: string[], ingredients: string[][], supplies: string[]): string[] {
    const adj = new Map<string, string[]>();
    const indeg = new Map<string, number>();
    for (let i = 0; i < recipes.length; i++) {
        indeg.set(recipes[i], ingredients[i].length);
        for (const ing of ingredients[i]) {
            if (!adj.has(ing)) adj.set(ing, []);
            adj.get(ing)!.push(recipes[i]);
        }
    }
    const q: string[] = [...supplies];
    const out: string[] = [];
    let head = 0;
    while (head < q.length) {
        const u = q[head++];
        const neighbors = adj.get(u);
        if (!neighbors) continue;
        for (const v of neighbors) {
            indeg.set(v, (indeg.get(v) ?? 0) - 1);
            if (indeg.get(v) === 0) {
                out.push(v);
                q.push(v);
            }
        }
    }
    return out;
}