トポロジカルソートで全部の講座を受けられるか調べる

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

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

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

from collections import deque
def can_finish(n, reqs):
    to = [[] for _ in range(n)]
    need = [0] * n
    for a, b in reqs:
        to[b].append(a)
        need[a] += 1
    queue = deque()
    for c in range(n):
        if need[c] == 0:
            queue.append(c)
    taken = 0
    while queue:
        c = queue.popleft()
        taken += 1
        for nx in to[c]:
            need[nx] -= 1
            if need[nx] == 0:
                queue.append(nx)
    return taken == n

function canFinish(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 queue = [];
  for (let c = 0; c < n; c++) {
    if (need[c] === 0) {
      queue.push(c);
    }
  }
  let head = 0;
  while (head < queue.length) {
    const c = queue[head];
    head++;
    for (const nx of to[c]) {
      need[nx]--;
      if (need[nx] === 0) {
        queue.push(nx);
      }
    }
  }
  return head === n;
}

func canFinish(
	n int, reqs [][]int,
) bool {
	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]++
	}
	queue := []int{}
	for c := 0; c < n; c++ {
		if need[c] == 0 {
			queue = append(queue, c)
		}
	}
	head := 0
	for head < len(queue) {
		c := queue[head]
		head++
		for _, nx := range to[c] {
			need[nx]--
			if need[nx] > 0 {
				continue
			}
			queue = append(queue, nx)
		}
	}
	return head == n
}