Course Schedule — có thể học hết các môn khi có ràng buộc tiên quyết không? Giải bằng topological sort thế nào?

Ý tưởng: Bài toán = phát hiện chu trình trong đồ thị có hướng. Dùng Kahn's algorithm (BFS theo bậc vào): bắt đầu từ các môn không có tiên quyết (in-degree 0), học dần và giảm in-degree hàng xóm. Nếu học được hết n môn thì không có chu trình.

Hình dung: bóc dần lớp môn "sẵn sàng học"; nếu còn môn nào kẹt vì phụ thuộc vòng tròn lẫn nhau thì không bao giờ in-degree về 0.

function canFinish(numCourses: number, prerequisites: number[][]): boolean {
  const indeg = new Array(numCourses).fill(0)
  const adj: number[][] = Array.from({ length: numCourses }, () => [])
  for (const [a, b] of prerequisites) { adj[b].push(a); indeg[a]++ }
  const queue = indeg.map((d, i) => i).filter(i => indeg[i] === 0)
  let done = 0
  while (queue.length) {
    const c = queue.shift()!
    done++
    for (const next of adj[c]) if (--indeg[next] === 0) queue.push(next)
  }
  return done === numCourses
}

Độ phức tạp: thời gian O(V+E), bộ nhớ O(V+E).

Lưu ý: Hướng cạnh dễ nhầm — [a, b] nghĩa "học b trước a", nên cạnh đi b → a. Cách DFS phát hiện chu trình bằng 3 màu (trắng/xám/đen) cũng phổ biến.

Idea: The problem = detecting a cycle in a directed graph. Use Kahn's algorithm (BFS by in-degree): start from courses with no prerequisites (in-degree 0), take them, and decrement neighbors' in-degree. If you can take all n courses, there's no cycle.

Picture it: peel off layers of "ready-to-take" courses; any course stuck in a mutual circular dependency never reaches in-degree 0.

function canFinish(numCourses: number, prerequisites: number[][]): boolean {
  const indeg = new Array(numCourses).fill(0)
  const adj: number[][] = Array.from({ length: numCourses }, () => [])
  for (const [a, b] of prerequisites) { adj[b].push(a); indeg[a]++ }
  const queue = indeg.map((d, i) => i).filter(i => indeg[i] === 0)
  let done = 0
  while (queue.length) {
    const c = queue.shift()!
    done++
    for (const next of adj[c]) if (--indeg[next] === 0) queue.push(next)
  }
  return done === numCourses
}

Complexity: time O(V+E), space O(V+E).

Note: Edge direction trips people up — [a, b] means "take b before a", so the edge goes b → a. The DFS 3-color (white/gray/black) cycle detection is also common.