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]