Course Schedule II: Topological Sort Tìm Thứ Tự Học Môn Học (Kahn/DFS)

Đề bài: Có n môn học (0..n-1) và prerequisite pairs [a, b] (học b trước mới học a được). Tìm một thứ tự học hợp lệ (topological order). Không thể thì trả về [].

Ví dụ: n=2, [[1,0]] → [0,1].

Giải pháp 1: Kahn's Algorithm (BFS + In-degree)

1. Tính in-degree cho mỗi node.
2. Queue các node in-degree = 0 (không có prerequisite).
3. Pop node, thêm vào kết quả, giảm in-degree của neighbors. Nếu neighbor in-degree = 0 → push queue.
4. Nếu kết quả length < n → có cycle → trả về [].

from collections import deque

class Solution:
    def findOrder(self, numCourses: int, prerequisites: list[list[int]]) -> list[int]:
        # Build graph và in-degree
        adj = [[] for _ in range(numCourses)]
        in_degree = [0] * numCourses
        for a, b in prerequisites:
            adj[b].append(a)
            in_degree[a] += 1
        
        # Queue các node in-degree 0
        q = deque([i for i in range(numCourses) if in_degree[i] == 0])
        order = []
        
        while q:
            u = q.popleft()
            order.append(u)
            for v in adj[u]:
                in_degree[v] -= 1
                if in_degree[v] == 0:
                    q.append(v)
        
        return order if len(order) == numCourses else []

# Test
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, [[0,1],[1,0]]))     # [] (cycle)

Giải pháp 2: DFS + Cycle Detection (Post-order)

DFS, đánh dấu: 0=unvisited, 1=visiting, 2=visited. Nếu gặp visiting → cycle. Thêm node vào stack sau khi visit xong children (post-order). Reverse stack = topological order.

class Solution:
    def findOrder(self, numCourses: int, prerequisites: list[list[int]]) -> list[int]:
        adj = [[] for _ in range(numCourses)]
        for a, b in prerequisites:
            adj[b].append(a)
        
        visited = [0] * numCourses  # 0=unvisited, 1=visiting, 2=done
        order = []
        has_cycle = False
        
        def dfs(u):
            nonlocal has_cycle
            if has_cycle:
                return
            visited[u] = 1
            for v in adj[u]:
                if visited[v] == 0:
                    dfs(v)
                elif visited[v] == 1:
                    has_cycle = True
                    return
            visited[u] = 2
            order.append(u)
        
        for i in range(numCourses):
            if visited[i] == 0:
                dfs(i)
            if has_cycle:
                return []
        
        return order[::-1]

So sánh

Kết luận

Topological sort là bài toán cốt lõi cho dependency resolution. Kahn's algorithm thường ưa dùng trong interview vì dễ giải thích và không lo stack overflow.