Pythonの並列コース

N個のコースがあり、これらに1からNまでのラベルが付けられているとします。また、関係配列を指定しました。ここで、relations [i] =[X、Y]は、コースXとコースYの間の前提条件の関係を表します。コースXはコースYの前に学習する必要があります。

私たちが勉強しているコースのすべての前提条件を勉強している限り、1学期で私たちはいくつものコースを勉強することができます。すべてのコースを勉強するために必要な学期の最小数を見つける必要があります。また、すべてのコースを学習する方法がない場合は、-1を返します。

したがって、入力がN =3、関係=[[1,3]、[2,3]]の場合、出力は2になります。最初の学期では、コース1と2が学習されます。後期には、コース3が学習されます。

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

• コース：=n

• 訪問：=サイズn + 1の配列、これをfalseで埋める

• キュー：=新しいリスト

• グラフ：=n+1サブリストのリスト

• in_degree：=サイズn + 1の配列で、これを0で埋めます

• 関係の各iについて、実行します

  • グラフの最後にi[1]を挿入します[i[0]]

  • in_degree [i [1]]：=in_degree [i [1]] + 1

• semeseter：=1

• 1からn+1の範囲のiの場合、実行

  • in_degree [i]がゼロの場合、

    • キューの最後にiを挿入します

    • 訪問した[i]：=True

• 学期：=1

• コース：=コース-キューのサイズ

• キューが空ではなく、コースがゼロ以外の場合は、実行してください

  • current_size：=キューのサイズ

  • current_sizeがゼロ以外の場合は、実行してください

    • current_course：=queue [0]

    • キューから最初の要素を削除する

    • current_size：=current_size-1

    • グラフ[current_course]の各iについて、実行

      • in_degree [i]：=in_degree [i]-1

      • iが訪問されておらず、in_degree [i]がゼロの場合、

        • コース：=コース-1

        • キューの最後にiを挿入します

        • 訪問した[i]：=真

  • 学期：=学期+ 1

• コースが0の場合は学期を返し、それ以外の場合は-1

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

例

class Solution(object):
   def minimumSemesters(self, n, relations):
      courses = n
      visited = [False for i in range(n+1)]
      queue = []
      graph = [[] for i in range(n+1)]
      in_degree = [0 for i in range(n+1)]
      for i in relations:
         graph[i[0]].append(i[1])
         in_degree[i[1]]+=1
      semeseter = 1
      for i in range(1,n+1):
         if not in_degree[i]:
            queue.append(i)
            visited[i] = True
         semester = 1
         courses -= len(queue)
         while queue and courses:
            current_size = len(queue)
            while current_size:
               current_course = queue[0]
               queue.pop(0)
               current_size-=1
               for i in graph[current_course]:
                  in_degree[i]-=1
                  if not visited[i] and not in_degree[i]:
                     courses-=1
                     queue.append(i)
                  visited[i]=True
            semester+=1
         return semester if not courses else -1

ob = Solution()
print(ob.minimumSemesters(3,[[1,3],[2,3]]))

入力

3, [[1,3],[2,3]]

出力

-1