Python 中的课程表 II

pythonserver side programmingprogramming更新于 2025/11/6 16:44:17

假设总共有 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]]))