Python课程表II

假设总共有n个路线，这些路线从0到n-1标记。某些课程可能具有先决条件，鉴于课程总数和先决条件对列表，我们必须找到完成所有课程应采取的课程顺序。可能有多个正确的订单，我们只需要找到其中一个即可。如果不可能完成所有课程，则返回一个空数组。

因此，如果输入为2 [[[1，0]]，则结果将为[0,1]。一共有2门课程。要选择课程1，我们应该已经完成课程0。因此正确的课程顺序是[0,1]

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

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

• 定义一个名为in_degree的数组，并填充所有节点的所有度数，以及图的adj：=邻接表

• 定义一个称为访问的数组，并用0填充，其大小与numCourses相同

• 定义一个空堆栈。

• 对于0到numCourses范围内的i

• 返回一个空列表

• 如果将访问堆栈传递到其中，则Visited [i]为假，而节点i的dfs为假，则

• 以相反的顺序返回堆栈元素。

示例

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

class Solution(object):
   def findOrder(self, numCourses, prerequisites):
      in_degree,adj=self.create_adj(numCourses,prerequisites)
      visited = [0 for i in range(numCourses)]
      stack = []
      for i in range(numCourses):
         if not visited[i] and not self.dfs(i,visited,stack,adj):
            return []
      return stack[::-1]
   def create_adj(self,n,graph):
      adj = {}
      in_degree= [0 for i in range(n)]
      for i in graph:
         in_degree[i[0]]+=1
         if i[1] in adj:
            adj[i[1]].append(i[0])
         else:
            adj[i[1]] = [i[0]]
      return in_degree,adj
   def dfs(self, node, visited,stack,adj):
      if visited[node] == -1:
         return False
      if visited[node] == 1:
         return True
      visited[node] = -1
      if node in adj:
         for i in adj[node]:
            if not self.dfs(i,visited,stack,adj):
               return False
      visited[node]=1
      stack.append(node)
      return True
ob = Solution()print(ob.findOrder(2, [[1,0]]))

输入项

2
[[1,0]]

输出结果

[0,1]