Python 中的并行课程

pythonserver side programmingprogramming更新于 2025/8/6 1:16:17

假设有 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

相关文章


有用资源