Python课程表

假设我们必须参加总共numCourses课程，从0到numCourses-1标记。某些课程可能有先决条件，例如，要选修课程0，我们必须首先选修课程1，该课程用一对表示：[0,1]。假设提供的课程总数和先决条件对列表，我们必须检查您是否有可能完成所有课程？

因此，如果输入类似于− numCourses = 2并且前提条件= [[1，0]]，那么结果将为true，因为总共要学习2门课程。要参加课程1，我们应该已经完成课程0。所以这是可能的。

为了解决这个问题，我们将遵循以下步骤-

• 在main方法中，将需要numCourses和先决条件：这将类似于-

• 如果前提条件没有条目，则返回true

• 制作一个名为visited的数组，并用0填充，其范围与numCourses相同

• adj_list：=使用先决条件创建图形

• 对于i范围从0到numCourses

• 如果图中的访问节点之间没有循环，则返回false

• 如果visit [i]为假，则

• 返回真

示例

让我们看下面的实现以更好地理解-

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]]))

输入值

2
[[1,0]]

输出结果

true