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