トポロジカルソートで手持ちの材料から作れる料理を全部見つける

from collections import deque


def possible_recipes(
    recipes, needs, stock
):
    # 料理ごとのそろっていない数
    left = {}
    pairs = []
    for i in range(len(needs)):
        r = recipes[i]
        left[r] = len(needs[i])
        for x in needs[i]:
            pairs.append((x, r))
    # 材料を使う料理
    users = {}
    for x, r in pairs:
        users.setdefault(x, [])
        users[x].append(r)
    q = deque(stock)
    made = []
    while q:
        x = q.popleft()
        rs = users.get(x, [])
        for r in rs:
            left[r] -= 1
            if left[r] == 0:
                made.append(r)
                q.append(r)
    return sorted(made)

function possibleRecipes(
  recipes, needs, stock,
) {
  // 料理ごとのそろっていない数
  const left = new Map();
  // 材料を使う料理
  const users = new Map();
  recipes.forEach((r, i) => {
    const k = needs[i].length;
    left.set(r, k);
    for (const x of needs[i]) {
      if (!users.has(x)) {
        users.set(x, []);
      }
      users.get(x).push(r);
    }
  });
  const q = [...stock];
  const made = [];
  for (const x of q) {
    for (const r of
      users.get(x) ?? []) {
      const k = left.get(r) - 1;
      left.set(r, k);
      if (k === 0) {
        made.push(r);
        q.push(r);
      }
    }
  }
  return made.sort();
}

import "sort"

func possibleRecipes(
	recipes []string,
	needs [][]string,
	stock []string,
) []string {
	// 料理ごとのそろっていない数
	left := map[string]int{}
	// 材料を使う料理
	users := map[string][]string{}
	for i, r := range recipes {
		left[r] = len(needs[i])
		for _, x := range needs[i] {
			users[x] = append(
				users[x], r)
		}
	}
	q := []string{}
	q = append(q, stock...)
	made := []string{}
	for i := 0; i < len(q); i++ {
		x := q[i]
		for _, r := range users[x] {
			left[r]--
			if left[r] == 0 {
				made = append(made, r)
				q = append(q, r)
			}
		}
	}
	sort.Strings(made)
	return made
}