Course Schedule II: หาลำดับเรียนวิชา (Topological Sort)

ตัวอย่าง: n=2, [[1,0]] → [0,1] (เรียน 0 ก่อน 1)

อัลกอริทึม: Topological Sort (Kahn's Algorithm / BFS)

1. สร้าง adjacency list และ indegree array
2. Queue ใส่โหนดที่ indegree = 0 (เรียนได้เลย)
3. Pop จาก queue → เพิ่มใน result → ลด indegree ของเพื่อนบ้าน → ถ้า indegree=0 push queue
4. ถ้า result มี n โหนด → สำเร็จ, มิฉะนั้นมี cycle → return []

การติดตั้ง (Python Implementation - Kahn's BFS)

from collections import deque

class Solution:
    def findOrder(self, numCourses: int, prerequisites: list[list[int]]) -> list[int]:
        # Build graph
        adj = [[] for _ in range(numCourses)]
        indegree = [0] * numCourses
        
        for course, pre in prerequisites:
            adj[pre].append(course)
            indegree[course] += 1
        
        # Kahn's algorithm
        q = deque([i for i in range(numCourses) if indegree[i] == 0])
        order = []
        
        while q:
            u = q.popleft()
            order.append(u)
            for v in adj[u]:
                indegree[v] -= 1
                if indegree[v] == 0:
                    q.append(v)
        
        return order if len(order) == numCourses else []

# ทดสอบ
ob = Solution()
print(ob.findOrder(2, [[1,0]]))              # [0, 1]
print(ob.findOrder(4, [[1,0],[2,0],[3,1],[3,2]]))  # [0,1,2,3] or [0,2,1,3]
print(ob.findOrder(2, [[1,0],[0,1]]))        # [] (cycle)

Output

[0, 1]
[0, 1, 2, 3]
[]

Alternative: DFS-based Topological Sort

class SolutionDFS:
    def findOrder(self, numCourses, prerequisites):
        adj = [[] for _ in range(numCourses)]
        for course, pre in prerequisites:
            adj[pre].append(course)
        
        visited = [0] * numCourses  # 0=unvisited, 1=visiting, 2=visited
        order = []
        
        def dfs(u):
            if visited[u] == 1:
                return False  # cycle
            if visited[u] == 2:
                return True
            visited[u] = 1
            for v in adj[u]:
                if not dfs(v):
                    return False
            visited[u] = 2
            order.append(u)
            return True
        
        for i in range(numCourses):
            if visited[i] == 0:
                if not dfs(i):
                    return []
        return order[::-1]  # reverse post-order

Complexity

• Time: O(V + E) โดย V = numCourses, E = prerequisites.length
• Space: O(V + E) สำหรับ adjacency list, indegree, queue/stack

สรุป

Course Schedule II = Topological Sort บน Directed Graph ใช้ Kahn's BFS (ง่าย ไม่ต้อง recursion) หรือ DFS (detect cycle ได้ชัดเจน) ทั้งคู่ O(V+E)

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