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

0からnumCourses-1までのラベルが付いた合計numCoursesコースがあるとします。一部のコースには前提条件がある場合があります。たとえば、コース0を受講するには、最初にコース1を受講する必要があります。これは、[0,1]のペアを使用して表されます。提供されているコースの総数と前提条件のペアのリストがあるとすると、すべてのコースを終了できるかどうかを確認する必要がありますか？

したがって、入力が− numCourses =2で、前提条件=[[1、0]]の場合、合計2つのコースがあるため、結果はtrueになります。コース1を受講するには、コース0を終了する必要があります。それで可能です。

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

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

  のように機能します。

• 前提条件にエントリがない場合は、trueを返します

• visitedという配列を作成し、これを0で埋めます。その範囲は、numCourses

  と同じです。

• adj_list：=前提条件を使用してグラフを作成する

• 0からnumCoursesの範囲のiの場合

  • visited [i]がfalseの場合、

    • グラフ内の訪問先ノード間にサイクルがない場合は、falseを返します

• trueを返す

例

理解を深めるために、次の実装を見てみましょう-

class Solution(object):
   def canFinish(self, numCourses, prerequisites):
      if len(prerequisites) == 0:
         return True
      visited = [0 for i in range(numCourses)]
      adj_list = self.make_graph(prerequisites)
      for i in range(numCourses):
         if not visited[i]:
            if not self.cycle(adj_list,visited,i):
               return False
      return True
   def cycle(self,adj_list,visited,current_node = 0):
      if visited[current_node] ==-1:
         return False
      if visited[current_node] == 1:
         return True
      visited[current_node] = -1
      if(current_node in adj_list):
         for i in adj_list[current_node]:
            if not self.cycle(adj_list,visited,i):
               return False
      visited[current_node] = 1
      return True
   def make_graph(self,array):
      adj_list = {}
      for i in array:
         if i[1] in adj_list:
            adj_list[i[1]].append(i[0])
         else:
            adj_list[i[1]] = [i[0]]
      return adj_list
ob = Solution()
print(ob.canFinish(2, [[1,0]]))

入力

2
[[1,0]]

出力

true