Các khóa học song song trong Python

Cho N khóa học (1 đến N) và mảng relations, relations[i] = [X, Y] nghĩa là khóa X phải học trước khóa Y. Mỗi học kỳ có thể học bao nhiêu khóa cũng được miễn là đã học đủ điều kiện tiên quyết. Tìm số học kỳ tối thiểu để học hết tất cả khóa. Nếu không thể → -1.

Ví dụ: N=3, relations=[[1,3],[2,3]] → 2 học kỳ (học kỳ 1: khóa 1,2; học kỳ 2: khóa 3).

Giải thuật (Topological Sort BFS)

• Xây dựng đồ thị và mảng in_degree
• Khởi tạo queue với các khóa in_degree = 0
• Mỗi vòng while queue: xử lý tất cả khóa trong queue hiện tại (một học kỳ)
• Giảm in_degree của khóa phụ thuộc, thêm vào queue khi in_degree = 0
• Đếm số học kỳ, nếu còn khóa chưa học → -1

Ví dụ triển khai

class Solution:
    def minimumSemesters(self, n, relations):
        courses = n
        visited = [False] * (n + 1)
        queue = []
        graph = [[] for _ in range(n + 1)]
        in_degree = [0] * (n + 1)
        for x, y in relations:
            graph[x].append(y)
            in_degree[y] += 1
        for i in range(1, n + 1):
            if in_degree[i] == 0:
                queue.append(i)
                visited[i] = True
        semester = 1
        courses -= len(queue)
        while queue and courses:
            current_size = len(queue)
            while current_size:
                current_course = queue.pop(0)
                current_size -= 1
                for nxt in graph[current_course]:
                    in_degree[nxt] -= 1
                    if not visited[nxt] and in_degree[nxt] == 0:
                        courses -= 1
                        queue.append(nxt)
                        visited[nxt] = True
            semester += 1
        return semester if courses == 0 else -1

ob = Solution()
print(ob.minimumSemesters(3, [[1, 3], [2, 3]]))

Đầu vào

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

Đầu ra

2