Course Schedule: ตรวจสอบว่าเรียนวิชาครบทุกวิชาได้หรือไม่ (Cycle Detection)

โจทย์

มี numCourses วิชา และ prerequisites [[course, pre], ...] ตรวจสอบว่า สามารถเรียนจบทุกวิชาได้หรือไม่ (คือ graph ไม่มี cycle)

ตัวอย่าง: 2, [[1,0]] → True (เรียน 0 แล้ว 1)

อัลกอริทึม: Cycle Detection ใน Directed Graph (DFS + 3 Colors)

• White (0): ยังไม่เยี่ยม
• Gray (1): กำลังเยี่ยม (อยู่ใน recursion stack) → พบ Gray อีกครั้ง = Cycle
• Black (2): เยี่ยมเสร็จแล้ว

การติดตั้ง (Python Implementation - DFS)

class Solution:
    def canFinish(self, numCourses: int, prerequisites: list[list[int]]) -> bool:
        # Build adjacency list
        adj = [[] for _ in range(numCourses)]
        for course, pre in prerequisites:
            adj[pre].append(course)
        
        # 0=unvisited, 1=visiting, 2=visited
        state = [0] * numCourses
        
        def has_cycle(u):
            if state[u] == 1:
                return True   # Cycle detected
            if state[u] == 2:
                return False  # Already processed
            
            state[u] = 1  # Mark visiting
            for v in adj[u]:
                if has_cycle(v):
                    return True
            state[u] = 2  # Mark visited
            return False
        
        for i in range(numCourses):
            if state[i] == 0:
                if has_cycle(i):
                    return False
        return True

# ทดสอบ
ob = Solution()
print(ob.canFinish(2, [[1,0]]))              # True
print(ob.canFinish(2, [[1,0],[0,1]]))        # False (cycle)
print(ob.canFinish(3, [[1,0],[2,1],[0,2]]))  # False (cycle 0→1→2→0)
print(ob.canFinish(4, [[1,0],[2,0],[3,1],[3,2]]))  # True

Output

True
False
False
True

Alternative: Kahn's Algorithm (BFS)

from collections import deque

def canFinish_kahn(numCourses, prerequisites):
    adj = [[] for _ in range(numCourses)]
    indegree = [0] * numCourses
    for course, pre in prerequisites:
        adj[pre].append(course)
        indegree[course] += 1
    
    q = deque([i for i in range(numCourses) if indegree[i] == 0])
    count = 0
    
    while q:
        u = q.popleft()
        count += 1
        for v in adj[u]:
            indegree[v] -= 1
            if indegree[v] == 0:
                q.append(v)
    
    return count == numCourses

Complexity

• Time: O(V + E)
• Space: O(V + E)

ความแตกต่าง Course Schedule I vs II

สรุป

Course Schedule เป็นโจทย์ Cycle Detection ใน Directed Graph มาตรฐาน ใช้ DFS 3-colors หรือ Kahn's BFS ได้ทั้งคู่ Course Schedule II ขยายให้คืน topological order ด้วย

หากมีข้อสงสัย สามารถถามได้ในส่วนความคิดเห็นครับ