PythonのコーススケジュールII

合計n個のコースがあり、これらには0からn-1までのラベルが付けられているとします。コースの総数と前提条件のペアのリストを考えると、一部のコースには前提条件がある場合があります。すべてのコースを完了するために必要なコースの順序を見つける必要があります。正しい注文が複数ある可能性があります。そのうちの1つを見つける必要があります。すべてのコースを終了できない場合は、空の配列を返します。

したがって、入力が2 [[1、0]]の場合、結果は[0,1]になります。受講するコースは全部で2つあります。コース番号1を受講するには、コース0を終了する必要があります。したがって、正しいコースの順序は[0,1]

これを解決するには、次の手順に従います-

• mainメソッドでは、numCoursesと前提条件が必要です。これは-

  のように機能します。

• in_degreeという配列を定義し、すべてのノードの次数をすべて入力し、adj：=グラフの隣接リスト

• 訪問先と呼ばれる1つの配列を定義し、これに0を入力します。そのサイズは、numCourses

  と同じです。

• 空のスタックを1つ定義します。

• 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]