数据结构
网络
关系型数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法学Python课程安排II
假设共有n门课程，编号从0到n-1。一些课程可能有先修课程，给定课程总数和先修课程对列表，我们必须找到完成所有课程的课程顺序。可能有多个正确的顺序，我们只需要找到其中一个。如果无法完成所有课程，则返回空数组。
因此，如果输入类似于2，[[1, 0]]，则结果将是[0,1]。共有2门课程需要学习。要学习课程编号1，我们应该已经完成了课程0。所以正确的课程顺序是[0,1]
为了解决这个问题，我们将遵循以下步骤：
在主方法中，它将采用numCourses和prerequisites：这将起到以下作用：
定义一个名为in_degree的数组，并填充所有节点的所有入度，adj := 图的邻接表
定义一个名为visited的数组，并用0填充它，其大小与numCourses相同
定义一个空栈。
对于范围0到numCourses中的i
如果visited[i]为false，并且通过将堆栈传递给它，节点i的dfs为false，则
返回空列表
以反序返回堆栈元素。
示例
让我们看看下面的实现，以便更好地理解：
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]
更新于：2020年4月29日
276 次浏览
广告