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