Python 中的并行课程
假设有 N 门课程,这些课程的标签从 1 到 N。我们还给出了一个关系数组,其中 relationships[i] = [X, Y],表示课程 X 和课程 Y 之间的先决条件关系。因此,这意味着课程 X 必须在课程 Y 之前学习。
在一个学期内,只要我们已经学习了所学课程的所有先决条件,我们就可以学习任意数量的课程。我们必须找到学习所有课程所需的最少学期数。如果没有办法学习所有课程,则返回 -1。
因此,如果输入为 N = 3,relations = [[1,3],[2,3]],则输出将为 2,因为在第一个学期,学习了课程 1 和 2。第二学期学习课程 3。
为了解决这个问题,我们将遵循以下步骤 −
courses := n
visited := 一个大小为 n+1 的数组,并用 false 填充
queue := 一个新列表
graph := 一个包含 n+1 个子列表的列表
in_degree := 一个大小为 n+1 的数组,并用 0 填充
对于关系中的每个 i,执行
在 graph[i[0]] 的末尾插入 i[1]
in_degree[i[1]] := in_degree[i[1]] + 1
semeseter := 1
对于范围从 1 到 n+1 的 i,执行
如果 in_degree[i] 为零,则
将 i 插入队列末尾
visited[i] := True
semester := 1
courses := courses - 队列大小
当队列不为空且 courses 非零时,执行
current_size := 队列大小
当 current_size非零,则执行
current_course :=queue[0]
从队列中删除第一个元素
current_size :=current_size - 1
对于 graph[current_course] 中的每个 i,执行
in_degree[i] :=in_degree[i] - 1
如果 i 未被访问且 in_degree[i] 为零,则
courses :=courses - 1
将 i 插入队列末尾
visited[i]:=真
semester := semester + 1
如果 courses 为 0,则返回 semester,否则返回 -1
让我们看看下面的实现以便更好地理解 −
示例
class Solution(object): def minimumSemesters(self, n, relations): courses = n visited = [False for i in range(n+1)] queue = [] graph = [[] for i in range(n+1)] in_degree = [0 for i in range(n+1)] for i in relations: graph[i[0]].append(i[1]) in_degree[i[1]]+=1 semeseter = 1 for i in range(1,n+1): if not in_degree[i]: 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[0] queue.pop(0) current_size-=1 for i in graph[current_course]: in_degree[i]-=1 if not visited[i] and not in_degree[i]: courses-=1 queue.append(i) visited[i]=True semester+=1 return semester if not courses else -1 ob = Solution() print(ob.minimumSemesters(3,[[1,3],[2,3]]))
输入
3, [[1,3],[2,3]]
输出
-1
相关文章
有用资源
python 参考教程 - 该教程包含有关 python 的更多信息:https://www.cainiaomax.com/python/

