Topological Sort

function canFinish(numCourses: number, prerequisites: number[][]): boolean {
  const adj: number[][] = Array.from({ length: numCourses }, () => []);
  const indegree = new Array<number>(numCourses).fill(0);
  for (const [course, prereq] of prerequisites) { adj[prereq].push(course); indegree[course]++; }
  const queue: number[] = [];
  for (let i = 0; i < numCourses; i++) if (indegree[i] === 0) queue.push(i);
  let head = 0, done = 0;          // index pointer, not shift() (O(1) dequeue)
  while (head < queue.length) {
    const node = queue[head++];
    done++;
    for (const nb of adj[node]) if (--indegree[nb] === 0) queue.push(nb);
  }
  return done === numCourses;
}

def can_finish?(num_courses, prerequisites)
  adj = Array.new(num_courses) { [] }
  indegree = Array.new(num_courses, 0)
  prerequisites.each do |course, prereq|
    adj[prereq] << course
    indegree[course] += 1
  end
  queue = (0...num_courses).select { |i| indegree[i].zero? }
  head = 0
  done = 0
  while head < queue.length # index pointer, not shift -> O(1) dequeue
    node = queue[head]
    head += 1
    done += 1
    adj[node].each do |nb|
      indegree[nb] -= 1
      queue << nb if indegree[nb].zero?
    end
  end
  done == num_courses
end