Python 中的课程表

pythonserver side programmingprogramming更新于 2025/11/6 16:12:17

假设我们需要修读的课程共有 numCourses 门，从 0 到 numCourses-1。有些课程可能有先决条件，例如要修读课程 0，我们必须先修读课程 1，这用一对来表示:[0,1]。假设提供的课程总数和先决条件对列表，我们必须检查您是否有可能完成所有课程?

因此，如果输入为 − numCourses = 2 和 prerequisites = [[1, 0]]，则结果将为 true，因为总共需要修读 2 门课程。要修读课程 1，我们必须先完成课程 0。所以这是可能的。

要解决这个问题，我们将遵循以下步骤 −

在主方法中，它将采用 numCourses 和先决条件:这将起到 − 的作用
如果先决条件没有条目，则返回 true
创建一个名为 accessed 的数组，用 0 填充，其范围与 numCourses 相同
adj_list := 使用先决条件创建图表
对于 i，范围为 0 到 numCourses
- 如果 accessed[i] 为 false，则
  - 如果图中访问的节点之间没有循环，则返回false
返回 true

示例

让我们看下面的实现，以便更好地理解 −

class Solution(object):
   def canFinish(self, numCourses, prerequisites):
      if len(prerequisites) == 0:
         return True
      visited = [0 for i in range(numCourses)]
      adj_list = self.make_graph(prerequisites)
      for i in range(numCourses):
         if not visited[i]:
            if not self.cycle(adj_list,visited,i):
               return False
      return True
   def cycle(self,adj_list,visited,current_node = 0):
      if visited[current_node] ==-1:
         return False
      if visited[current_node] == 1:
         return True
      visited[current_node] = -1
      if(current_node in adj_list):
         for i in adj_list[current_node]:
            if not self.cycle(adj_list,visited,i):
               return False
      visited[current_node] = 1
      return True
   def make_graph(self,array):
      adj_list = {}
      for i in array:
         if i[1] in adj_list:
            adj_list[i[1]].append(i[0])
         else:
            adj_list[i[1]] = [i[0]]
      return adj_list
ob = Solution()
print(ob.canFinish(2, [[1,0]]))