Python并行课程
假设有N个课程,它们的编号从1到N。我们还给出了一个关系数组,其中关系[i]=[X,Y]表示课程X和课程Y之间的先决条件关系。因此,这意味着X课程必须在Y课程之前学习。
一个学期,只要我们已经学习了所学课程的所有前提条件,就可以学习任何数量的课程。我们必须找到学习所有课程所需的最少学期数。如果无法学习所有课程,则返回-1。
因此,如果输入像N=3,关系=[[1,3],[2,3]],则输出将为2,因为在第一学期,研究课程1和2。在第二学期,学习课程3。
为了解决这个问题,我们将遵循以下步骤-
课程:=n
Visited:=一个大小为n+1的数组,并用false填充它
队列:=一个新列表
图:=n+1子列表的列表
in_degree:=大小为n+1的数组,并用0填充
对于关系中的每个我,
在图[i[0]]的末尾插入i[1]
in_degree[i[1]]:=in_degree[i[1]]+1
semeseter:=1
对于范围1到n+1的i
在队列末尾插入i
访问过[i]:=正确
如果in_degree[i]为零,则
学期:=1
课程:=课程-队列大小
当队列不为空且课程非零时,执行
current_course:=队列[0]
从队列中删除第一个元素
current_size:=current_size-1
对于图[current_course]中的每个i,执行
课程:=课程-1
在队列末尾插入i
Visited[i]:=真
in_degree[i]:=in_degree[i]-1
如果未访问i并且in_degree[i]为零,则
current_size:=队列大小
当current_size不为零时,执行
学期:=学期+1
如果课程为0,则返回学期,否则为-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