207. Course Schedule
Tags:
Medium
Skills:
GraphTopological Sort
June 24, 2025
04:32 AM
No headings found
Loading content...
Related Posts
Leetcode
No headings found
Related Posts
Leetcode
Problem
Bài toán yêu cầu kiểm tra xem có thể hoàn thành tất cả các khóa học nếu biết trước các mối quan hệ tiên quyết giữa các khóa học. Về bản chất, đây là bài toán kiểm tra chu trình trong đồ thị có hướng (directed graph cycle detection)
Hay cụ thể hơn là kiểm tra xem đồ thị có phải là đồ thị có hướng không chu trình hay không (DAG)
Phân tích
- Mỗi khóa học là một node trong đồ thị
- Mỗi cặp
[a, b]nghĩa là muốn học a phải học xong b, tức là có cạnh từb -> a - Nếu tồn tại chu trình (cycles) sẽ không thể hoàn thành tất cả khóa học
- Nếu không có cycles, ta có thể hoàn thành tất cả các khóa học
Approach
Có hai cách phổ biến:
- Dùng BFS với Topological Sort (Kahn's Algorithm): Đếm số lượng đỉnh có thể lấy được theo thứ tự không có chu trình.
- Dùng DFS để phát hiện chu trình: Đánh dấu trạng thái các node khi duyệt.
Ở đây, phương pháp Topological Sort bằng BFS là tối ưu và dễ hiểu cho bài này.
Solution - Topo - BFS
typescripttypescript
1function canFinish(numCourses: number, prerequisites: number[][]): boolean {
2 let graph: Map<number, number[]> = new Map();
3 let inDegree = new Array(numCourses).fill(0);
4
5 for (const [course, prere] of prerequisites) {
6 if (!graph.has(prere)) {
7 graph.set(prere, [])
8 }
9 graph.get(prere)!.push(course);
10 inDegree[course]++
11 }
12
13 let order: number[] = []
14 let queue: number[] = [];
15 for (let i = 0; i < numCourses; i++) {
16 if (inDegree[i] === 0) {
17 queue.push(i)
18 }
19 }
20
21 while (queue.length > 0) {
22 let course = queue.shift()!;
23 order.push(course);
24 for (const newCourse of graph.get(course)! || []) {
25 inDegree[newCourse]--;
26 if (inDegree[newCourse] === 0) {
27 queue.push(newCourse);
28 }
29 }
30 }
31
32 return order.length === numCourses ? true : false
33};