Python 中的课程表 II
pythonserver side programmingprogramming更新于 2023/10/8 4:52:00
假设总共有 n 门课程，这些课程的编号从 0 到 n-1。有些课程可能有先修课程，给定课程总数和先修课程对列表，我们必须找到完成所有课程所需的课程顺序。可能有多个正确的顺序，我们只需找到其中一个即可。如果不可能完成所有课程，则返回一个空数组。
因此，如果输入为 2, [[1, 0]]，则结果将为 [0,1]。总共有 2 门课程需要修读。要选修 1 号课程，我们必须先完成 0 号课程。因此正确的课程顺序是 [0,1]
要解决这个问题，我们将遵循以下步骤 −
在主方法中，它将采用 numCourses 和先决条件:这将起到 − 的作用
定义一个名为 in_degree 的数组，并用所有节点的度数填充，adj := 图的邻接列表
定义一个名为 accessed 的数组，并用 0 填充，其大小与 numCourses 相同
定义一个空堆栈。
对于 0 到 numCourses 范围内的 i
如果 accessed[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]
