Chương trình đếm số học kỳ tối thiểu để học hết các khóa học trong Python

Cho n khóa học (1..n), mảng relations với relations[i] = (prev, next) (prev phải học trước next). Mỗi học kỳ học tối đa k khóa, miễn là đã học đủ điều kiện tiên quyết. Tìm số học kỳ tối thiểu.

Ví dụ: n=6, relations=[(1,3),(2,5),(2,4),(5,6)], k=2 → 3 học kỳ. Kỳ 1: học 1,2; Kỳ 2: học 5 và 3 (hoặc 4); Kỳ 3: học phần còn lại.

Giải thuật (Topological sort + heuristic)

1. Xây đồ thị: g1[i] = danh sách tiên quyết của i, g2[i] = danh sách khóa phụ thuộc vào i.
2. Tính weight[i] = len(g1[i]) (số tiên quyết).
3. Lan truyền trọng số: w[x] = max(w[x], weight[i]) cho x trong g1[i].
4. Lặp cho đến khi học đủ n khóa:
   • Thu thập khóa sẵn sàng (g1[i] rỗng, chưa học).
   • Nếu > k khóa: sắp xếp giảm dần theo w[i], lấy k khóa đầu.
   • Cập nhật đồ thị: xóa khóa đã học khỏi g1 của các khóa phụ thuộc.
   • Tăng số học kỳ.

Ví dụ minh họa

def solve(n, relations, k):
    taken = set()
    g1 = [[] for _ in range(n)]
    g2 = [[] for _ in range(n)]
    w = [0] * n
    semester = 0
    for x in relations:
        g1[x[1]-1].append(x[0]-1)
        g2[x[0]-1].append(x[1]-1)
    weight = list(map(len, g1))
    for i in range(n):
        for x in g1[i]:
            w[x] = max(w[x], weight[i])
    while len(taken) < n:
        courses = []
        for i in range(n):
            if not g1[i] and i not in taken:
                courses.append([i, w[i]])
        if len(courses) > k:
            courses = sorted(courses, key=lambda x: x[1], reverse=True)
            courses = courses[:k]
        semester += 1
        for x in courses:
            for y in g2[x[0]]:
                g1[y].remove(x[0])
            g2[x[0]] = []
            taken.add(x[0])
    return semester

n = 6
relations = [(1,3),(2,5),(2,4),(5,6)]
k = 2
print(solve(n, relations, k))

Đầu vào

6, [(1,3),(2,5),(2,4),(5,6)], 2

Đầu ra

3