Có tổng cộng numCourses khóa học bạn cần hoàn thành, đánh số từ 0 đến numCourses - 1. Cho mảng prerequisites trong đó prerequisites[i] = [a, b] thể hiện rằng bạn phải hoàn thành khóa học b trước khi học khóa học a.
Hãy xác định xem có thể hoàn thành tất cả các khóa học hay không (đồ thị có chứa chu trình hay không).
Ví dụ 1:
Input: numCourses = 2, prerequisites = [[1, 0]]
Output: true
Giải thích: Học 0 trước, sau đó học 1.Ví dụ 2:
Input: numCourses = 2, prerequisites = [[1, 0], [0, 1]]
Output: false
Giải thích: Chu trình phụ thuộc vòng quanh.Định Dạng Đầu Vào (Input)
Dòng 1: Số nguyên numCourses
Dòng 2: Mảng prerequisites
Dòng 2: Mảng prerequisites
Định Dạng Đầu Ra (Output)
true hoặc false
Ràng Buộc (Constraints)
1 <= numCourses <= 2000
Ví Dụ Kiểm Thử Mẫu
Ví dụ 1:
Input:
2
[[1, 0]]
Output:
true
Giải thích: Học được
Ví dụ 2:
Input:
2
[[1, 0], [0, 1]]
Output:
false
Giải thích: Vòng luẩn quẩn
Gợi ý được sắp xếp theo cấp độ tiến dần. Hãy mở từng gợi ý khi bạn thực sự cần thêm định hướng.
Kahn's Algorithm (Topological Sort BFS) O(V + E)
Dùng mảng in-degree (bán bậc vào). Đưa các khóa học có bán bậc vào bằng 0 vào queue. Duyệt queue và giảm bậc vào của các môn liên quan.
Dữ liệu đầu vào (Input):
2
[[1, 0]]
Kết quả kỳ vọng (Expected Output):
true
Dữ liệu đầu vào (Input):
2
[[1, 0], [0, 1]]
Kết quả kỳ vọng (Expected Output):
false
Nhập STDIN của bạn (Mỗi dòng một tham số):
Bấm Chạy thử để kiểm tra các bộ test mẫu hoặc Nộp bài để chấm điểm chính thức.
Đang gửi mã và thực thi trên Sandbox Engine...
