难度: Medium
Submission
运行时间: 41 ms
内存: 18.1 MB
class Solution:
def minimumSemesters(self, n: int, relations: List[List[int]]) -> int:
# Create a default dictionary to hold the adjacency list representation of the graph
graph = defaultdict(list)
# Initialize a list for incoming degree count of each node
incoming_degree = [0] * n
# Populate the graph and update the incoming degree counts
for prereq, course in relations:
# Adjust indices to be 0-based instead of 1-based
prereq -= 1
course -= 1
graph[prereq].append(course)
incoming_degree[course] += 1
# Initialize a queue with all courses having 0 incoming degree
queue = deque([i for i, degree in enumerate(incoming_degree) if degree == 0])
# Initialize a variable to count the number of semesters
semesters = 0
# Process nodes level by level (BFS)
while queue:
# Increment the semester count
semesters += 1
# Process all nodes in the current level
for _ in range(len(queue)):
course = queue.popleft()
n -= 1 # Decrement the number of courses remaining
# Decrease the incoming degree of all adjacent courses
for next_course in graph[course]:
incoming_degree[next_course] -= 1
# If adjacent course has no more prerequisites, add it to the queue
if incoming_degree[next_course] == 0:
queue.append(next_course)
# If all courses are covered, return the number of semesters
# If there are still courses remaining with nonzero incoming degree,
# it means there's a cycle, and we return -1 to indicate it's not possible to finish
return semesters if n == 0 else -1
Explain
该解法采用了拓扑排序的思想来解决课程安排的问题。首先，使用一个邻接表来表示课程之间的依赖关系，并用一个数组来跟踪每个课程的入度（即有多少其他课程依赖于该课程）。通过遍历所有的课程关系来构建这两个数据结构。接下来，使用一个队列来实现广度优先搜索（BFS），初始化时将所有入度为0的课程加入队列，表示这些课程没有任何先修课程，可以在第一个学期学习。在每个学期，从队列中依次取出当前可学的课程，对于每个取出的课程，将其所有后续课程的入度减1，如果某后续课程的入度减为0，则将其加入队列，表示下一学期可以学习。过程中记录学期数。如果最终所有课程都被学习（即所有课程都被加入过队列并处理），则返回总学期数；如果存在课程由于依赖关系（如循环依赖）无法完成，则返回-1。
时间复杂度: O(V + E)
空间复杂度: O(V + E)
class Solution:
def minimumSemesters(self, n: int, relations: List[List[int]]) -> int:
graph = defaultdict(list) # 存储课程依赖关系的邻接表
incoming_degree = [0] * n # 存储每个课程的入度
for prereq, course in relations:
prereq -= 1 # 由于课程编号从1开始，调整为0开始
course -= 1
graph[prereq].append(course) # 建立从先修课程到课程的边
incoming_degree[course] += 1 # 更新课程的入度
queue = deque([i for i, degree in enumerate(incoming_degree) if degree == 0]) # 入度为0的课程可以首先学习
semesters = 0
while queue:
semesters += 1 # 开始新的一学期
for _ in range(len(queue)):
course = queue.popleft()
n -= 1 # 处理一个课程
for next_course in graph[course]:
incoming_degree[next_course] -= 1 # 减少后继课程的入度
if incoming_degree[next_course] == 0:
queue.append(next_course) # 如果后继课程入度为0，加入队列
return semesters if n == 0 else -1 # 如果所有课程都被处理，返回学期数，否则由于存在环，返回-1
Explore
在拓扑排序中，如果存在循环依赖，意味着不可能完成所有课程的学习。算法通过检查是否所有课程都被加入和处理过来检测循环依赖。具体来说，在算法中我们使用一个计数器`n`来跟踪还未处理的课程数量。每处理完一个课程，计数器`n`减1。如果在所有课程都入队并出队处理（即拓扑排序正常进行）后，`n`变为0，则表示没有循环依赖，可以完成所有课程。如果在队列为空时`n`不为0，说明存在未能加入队列的课程，这通常是由于这些课程形成了循环依赖导致的。因此，此时算法会返回-1，表示课程安排存在问题，无法完成学习。
在构建图的邻接表时，使用`defaultdict(list)`而不是普通的字典主要是为了编码方便和效率。使用`defaultdict(list)`可以自动为尚未存在的键创建一个空列表，这样在添加边时无需检查键是否已经存在于字典中。如果使用普通字典，每次添加边时都需要先检查并可能初始化键，这会增加代码的复杂性和运行时的操作。此外，`defaultdict(list)`性能良好，适合频繁的插入操作，是构建邻接表的理想选择。
每个课程的入度表示有多少其他课程依赖于该课程先修完成。在算法中，我们首先将所有课程的入度初始化为0。然后，遍历给定的课程依赖关系列表`relations`，每当一个课程B依赖于课程A时（即A是B的先修课程），我们就将课程B的入度增加1。这个过程通过`incoming_degree[course] += 1`实现，其中`course`是从先修关系中得到的依赖课程的编号。通过这种方式，所有课程的入度在遍历所有依赖关系后正确地反映了各自的依赖数量。
算法通过拓扑排序确保如果可能，所有课程都可以被完成。在拓扑排序中，入度为0的课程意味着它们没有未完成的先修课程，因此可以立即开始学习。这些课程首先被加入队列并在每个学期被处理。每处理一个课程，就会检查该课程的所有后续课程，将其入度减1，如果某后续课程的入度因此减为0，它就可以在下一个学期学习，因此被加入队列。如果算法执行结束时，仍有课程的入度不为0（即没有被加入队列），这意味着存在一些因为依赖关系未被解决而无法开始学习的课程。这通常是因为这些课程之间形成了循环依赖。在这种情况下，算法会返回-1，表示由于课程之间的循环依赖，无法完成所有课程的安排。这个机制确保只有在所有课程都可以合理安排时，才会返回总学期数。