1
class Solution:
2
    def minNumberOfSemesters(self, n: int, relations: List[List[int]], k: int) -> int:
3
        graph = [0] * n
4
        out_degree = [0] * n
5
        # -1 to fix 1-based indexing offset from prompt.
6
        for pre_req, course in relations:
7
            graph[course - 1] += 1 << (pre_req - 1)
8
            out_degree[pre_req - 1] += 1
9
        # Just converts course to its shifted value
10
        c2shift = [1 << course for course in range(n)]
11
        start = 0
12
        goal = 2**n - 1  # will eq course_total once all have been taken.
13
        queue = collections.deque([(start, 0)])
14
        seen = [0] * (2**n)
15

16
        # Similar to Bellman-Ford
17
        while queue:
18
            # course_total is state. Each bit representing a taken course.
19
            course_total, steps = queue.popleft()
20
            available = []
21
            for course_num in range(n):
22
                if (course_total & graph[course_num] == graph[course_num]) and (
23
                    course_total & c2shift[course_num] == 0
24
                ):
25
                    available.append(course_num)
26

27
            # pre_req courses can unlock others.
28
            pre_reqs = [
29
                c2shift[course_num]
30
                for course_num in available
31
                if out_degree[course_num]
32
            ]
33
            leaves = [
34
                c2shift[course_num]
35
                for course_num in available
36
                if out_degree[course_num] == 0
37
            ]
38

39
            # We only include leaf courses when we have extra space
40
            if len(pre_reqs) <= k:
41
                course_total += sum(pre_reqs) + sum(leaves[: k - len(pre_reqs)])
42
                if course_total == goal:
43
                    return steps + 1
44
                if not seen[course_total]:
45
                    queue.append((course_total, steps + 1))
46
                    seen[course_total] = 1
47
            else:
48
                # Trying every combination of the pre_reqs.
49
                # comb is required here because we can't simply take them all (len(pre_reqs) > k)
50
                for batch in itertools.combinations(pre_reqs, k):
51
                    diff = sum(batch)
52
                    t = course_total + diff
53
                    if t == goal:
54
                        return steps + 1
55
                    if not seen[t]:
56
                        queue.append((t, steps + 1))
57
                        seen[t] = 1