Đề bài: Cho numCourses và prerequisites [a, b] (học b trước a). Kiểm tra có thể học hết tất cả môn không (tức là đồ thị KHÔNG có cycle).
Ví dụ: 2, [[1,0]] → True. 2, [[0,1],[1,0]] → False.
Giải pháp: DFS Cycle Detection (3 trạng thái)
Trạng thái node: 0=unvisited, 1=visiting (trong call stack hiện tại), 2=visited (done).
- DFS từ mỗi node unvisited.
- Nếu gặp neighbor đang
visiting (1)→ có back edge → cycle → return False. - Nếu neighbor
visited (2)→ đã kiểm tra, bỏ qua. - Sau khi DFS xong children → mark
2.
Code Python
class Solution:
def canFinish(self, numCourses: int, prerequisites: list[list[int]]) -> bool:
# Build adjacency list
adj = [[] for _ in range(numCourses)]
for a, b in prerequisites:
adj[b].append(a)
visited = [0] * numCourses # 0=unvisited, 1=visiting, 2=done
def has_cycle(u):
if visited[u] == 1:
return True # Back edge -> cycle
if visited[u] == 2:
return False # Already processed, no cycle from here
visited[u] = 1
for v in adj[u]:
if has_cycle(v):
return True
visited[u] = 2
return False
for i in range(numCourses):
if visited[i] == 0:
if has_cycle(i):
return False
return True
# Test
ob = Solution()
print(ob.canFinish(2, [[1,0]])) # True
print(ob.canFinish(2, [[0,1],[1,0]])) # False
print(ob.canFinish(3, [[1,0],[2,1],[0,2]])) # False (cycle 0->1->2->0)
Giải pháp thay thế: Kahn's Algorithm (BFS)
Đếm in-degree, queue in-degree=0, pop và giảm in-degree neighbor. Nếu processed count == n → no cycle.
from collections import deque
def canFinish(self, numCourses, prerequisites):
adj = [[] for _ in range(numCourses)]
in_deg = [0] * numCourses
for a, b in prerequisites:
adj[b].append(a)
in_deg[a] += 1
q = deque([i for i in range(numCourses) if in_deg[i] == 0])
count = 0
while q:
u = q.popleft()
count += 1
for v in adj[u]:
in_deg[v] -= 1
if in_deg[v] == 0:
q.append(v)
return count == numCourses
Phân tích
- Time:
O(V + E) - Space:
O(V + E) - DFS: recursion depth có thể gây stack overflow nếu V lớn (Python default ~1000). Kahn an toàn hơn.
Kết luận
Course Schedule = Cycle Detection in Directed Graph. DFS 3-color hoặc Kahn's algorithm đều chuẩn. Kahn khuyến khích cho production/large graph.