トポロジカルソートとヒープで講座を受ける順を決める

n = 5
reqs = [[4, 1], [2, 1],
  [3, 4], [3, 2]]

n = 5
reqs = [[1, 4], [0, 2]]

n = 3
reqs = [[0, 1], [1, 0]]

import heapq
def course_order(n, reqs):
    to = [[] for _ in range(n)]
    need = [0] * n
    for a, b in reqs:
        to[b].append(a)
        need[a] += 1
    push = heapq.heappush
    pop = heapq.heappop
    ready = []
    for c in range(n):
        if need[c] == 0:
            push(ready, c)
    order = []
    while ready:
        c = pop(ready)
        order.append(c)
        for nx in to[c]:
            need[nx] -= 1
            if need[nx] == 0:
                push(ready, nx)
    if len(order) < n:
        return []
    return order

function heapPush(h, v) {
  h.push(v);
  let i = h.length - 1;
  while (i > 0) {
    const p = (i - 1) >> 1;
    if (h[p] <= h[i]) break;
    [h[p], h[i]] = [h[i], h[p]];
    i = p;
  }
}

function heapPop(h) {
  const top = h[0];
  const last = h.pop();
  if (h.length === 0) {
    return top;
  }
  h[0] = last;
  let i = 0;
  while (true) {
    let m = i;
    const l = 2 * i + 1;
    const r = l + 1;
    if (l < h.length) {
      if (h[l] < h[m]) m = l;
    }
    if (r < h.length) {
      if (h[r] < h[m]) m = r;
    }
    if (m === i) return top;
    [h[m], h[i]] = [h[i], h[m]];
    i = m;
  }
}

function courseOrder(
  n, reqs
) {
  const to = [];
  const need = [];
  for (let c = 0; c < n; c++) {
    to.push([]);
    need.push(0);
  }
  for (const [a, b] of reqs) {
    to[b].push(a);
    need[a]++;
  }
  const ready = [];
  for (let c = 0; c < n; c++) {
    if (need[c] === 0) {
      heapPush(ready, c);
    }
  }
  const order = [];
  while (ready.length > 0) {
    const c = heapPop(ready);
    order.push(c);
    for (const nx of to[c]) {
      need[nx]--;
      if (need[nx] === 0) {
        heapPush(ready, nx);
      }
    }
  }
  if (order.length < n) {
    return [];
  }
  return order;
}

import "container/heap"

type minHeap []int

func (h minHeap) Len() int {
	return len(h)
}

func (h minHeap) Less(
	i, j int,
) bool {
	return h[i] < h[j]
}

func (h minHeap) Swap(
	i, j int,
) {
	h[i], h[j] = h[j], h[i]
}

func (h *minHeap) Push(x any) {
	*h = append(*h, x.(int))
}

func (h *minHeap) Pop() any {
	old := *h
	last := len(old) - 1
	v := old[last]
	*h = old[:last]
	return v
}

func courseOrder(
	n int, reqs [][]int,
) []int {
	to := make([][]int, n)
	need := make([]int, n)
	for _, p := range reqs {
		a, b := p[0], p[1]
		to[b] = append(to[b], a)
		need[a]++
	}
	ready := &minHeap{}
	for c := 0; c < n; c++ {
		if need[c] == 0 {
			heap.Push(ready, c)
		}
	}
	order := []int{}
	for ready.Len() > 0 {
		c := heap.Pop(ready).(int)
		order = append(order, c)
		for _, nx := range to[c] {
			need[nx]--
			if need[nx] == 0 {
				heap.Push(ready, nx)
			}
		}
	}
	if len(order) < n {
		return []int{}
	}
	return order
}