Leetcode举一反三第二期---课程规划和 BFS的熟悉掌握

from collections import deque

class Solution:
    def canFinish(self, numCourses: int, prerequisites: list[list[int]]) -> bool:
        # 1. 建图：入度数组 + 邻接表
        indegree = [0] * numCourses
        adj = [[] for _ in range(numCourses)]

        for course, pre in prerequisites:
            adj[pre].append(course)  # pre -> course
            indegree[course] += 1

        # 2. 入度为 0 的课程先入队
        queue = deque([i for i in range(numCourses) if indegree[i] == 0])

        visited_count = 0

        # 3. BFS
        while queue:
            curr = queue.popleft()
            visited_count += 1

            for next_course in adj[curr]:
                indegree[next_course] -= 1
                if indegree[next_course] == 0:
                    queue.append(next_course)

        # 4. 能出队的课程数等于总数，说明没有环
        return visited_count == numCourses

from collections import deque

class Solution:
    def findOrder(self, numCourses: int, prerequisites: list[list[int]]) -> list[int]:
        indegree = [0] * numCourses
        adj = [[] for _ in range(numCourses)]

        for course, pre in prerequisites:
            adj[pre].append(course)
            indegree[course] += 1

        queue = deque([i for i in range(numCourses) if indegree[i] == 0])

        # 【修改 1】：计数器 visited_count 换成结果列表 res
        res = []

        while queue:
            curr = queue.popleft()

            # 【修改 2】：出队时把课程追加进 res，出队顺序本身就是拓扑序
            res.append(curr)

            for next_course in adj[curr]:
                indegree[next_course] -= 1
                if indegree[next_course] == 0:
                    queue.append(next_course)

        # 【修改 3】：返回值由 bool 改成列表，有环时 res 不满，返回 []
        return res if len(res) == numCourses else []

from collections import deque

class Solution:
    def minimumSemesters(self, n: int, relations: list[list[int]]) -> int:
        # 【修改 1】：课程编号从 1 开始，数组开 n + 1
        # 注意 relations 是 [prev, next]，跟 207 里的 [course, pre] 顺序相反
        indegree = [0] * (n + 1)
        adj = [[] for _ in range(n + 1)]

        for pre, course in relations:
            adj[pre].append(course)
            indegree[course] += 1

        queue = deque([i for i in range(1, n + 1) if indegree[i] == 0])

        visited_count = 0
        semesters = 0  # 【修改 2】：新增学期计数

        while queue:
            semesters += 1  # 【修改 3】：每处理完一整层，就是一个学期

            for _ in range(len(queue)):  # 【修改 3】：按层遍历，固定本层大小
                curr = queue.popleft()
                visited_count += 1

                for next_course in adj[curr]:
                    indegree[next_course] -= 1
                    if indegree[next_course] == 0:
                        queue.append(next_course)

        # 【修改 4】：没修完说明有环返回 -1，否则返回层数
        return semesters if visited_count == n else -1

from collections import deque

class Solution:
    def minimumTime(self, n: int, relations: list[list[int]], time: list[int]) -> int:
        indegree = [0] * (n + 1)
        adj = [[] for _ in range(n + 1)]

        for pre, course in relations:
            adj[pre].append(course)
            indegree[course] += 1

        # 【修改 1】：finish[i] 表示课程 i 最早能在第几个月修完
        finish = [0] * (n + 1)

        queue = deque()
        for i in range(1, n + 1):
            if indegree[i] == 0:
                queue.append(i)
                finish[i] = time[i - 1]  # 【修改 2】：起点课程的完成时间就是自身耗时

        while queue:
            curr = queue.popleft()

            for next_course in adj[curr]:
                # 【修改 3】：等最晚的那门前置课修完，再加自己的耗时
                finish[next_course] = max(finish[next_course], finish[curr] + time[next_course - 1])

                indegree[next_course] -= 1
                if indegree[next_course] == 0:
                    queue.append(next_course)

        # 【修改 4】：题目保证无环，不用计数，所有课程里最晚完成的时间就是答案
        return max(finish)