Phát hiện phụ thuộc vòng bằng Topological Sort

Mục tiêu kiến thức

• Thuật toán Kahn (Sắp xếp Tô-pô dựa trên bán bậc vào In-degree và Hàng đợi).
• Phát hiện chu trình trong đồ thị có hướng (Directed Cycle Detection).
• Áp dụng kiểm tra Deadlock / Vòng lặp phụ thuộc trong các pipeline phần mềm.

Mô tả bài toán

Chương trình đào tạo tại AI Empire Academy bao gồm num_courses khóa học được đánh số từ 0 đến num_courses - 1. Một số khóa học có yêu cầu tiên quyết: để học khóa u, học viên phải hoàn thành khóa v trước, ký hiệu bằng cặp (u, v) trong danh sách prerequisites.

Hãy viết hàm can_finish_courses(num_courses: int, prerequisites: list[tuple[int, int]]) -> bool xác định xem học viên có thể hoàn thành toàn bộ các khóa học hay không (tức là không tồn tại bất kỳ vòng phụ thuộc luẩn quẩn nào như A yêu cầu B, B lại yêu cầu A).

Thuật toán Kahn:

• Đếm bán bậc vào (in_degree) của từng môn học.
• Đưa tất cả các môn học có in_degree == 0 (không có điều kiện tiên quyết) vào hàng đợi.
• Liên tục lấy một môn ra khỏi hàng đợi, tăng số môn hoàn thành lên 1, và giảm in_degree của các môn phụ thuộc vào nó. Nếu môn nào giảm về 0 thì đưa vào hàng đợi.
• Nếu tổng số môn hoàn thành đúng bằng num_courses, trả về True; ngược lại (còn chu trình bế tắc), trả về False.

Ràng buộc

• 1 ≤ num_courses ≤ 2000.
• 0 ≤ len(prerequisites) ≤ 5000.
• Thời gian chạy tối đa: 1000ms.
• Giới hạn bộ nhớ: 256MB.