Fb

[leetcode] 210。コーススケジュールII



210 Course Schedule Ii



説明

0からn-1までのラベルが付いた合計nのコースを受講する必要があります。

一部のコースには前提条件がある場合があります。たとえば、コース0を受講するには、最初にコース1を受講する必要があります。これはペアとして表されます：[0,1]



コースの総数と前提条件のペアのリストを前提として、すべてのコースを完了するために受講する必要のあるコースの順序を返します。

正しい注文が複数ある場合があります。そのうちの1つを返品するだけです。すべてのコースを終了できない場合は、空の配列を返します。



例1：

Input: 2, [[1,0]] Output: [0,1] Explanation: There are a total of 2 courses to take. To take course 1 you should have finished course 0. So the correct course order is [0,1] .

例2：

Input: 4, [[1,0],[2,0],[3,1],[3,2]] Output: [0,1,2,3] or [0,2,1,3] Explanation: There are a total of 4 courses to take. To take course 3 you should have finished both courses 1 and 2. Both courses 1 and 2 should be taken after you finished course 0. So one correct course order is [0,1,2,3]. Another correct ordering is [0,2,1,3] .

注意：



  1. 入力の前提条件は、隣接行列ではなく、エッジのリストで表されるグラフです。グラフの表現方法の詳細をご覧ください。
  2. 入力の前提条件に重複するエッジがないと想定する場合があります。

分析

タイトルの意味は次のとおりです。いくつかのコースを提供し、コースは順番に教えられ、トピックはあなたが勉強するためのものです。

  • まず、コースはノードを表し、コースとコースの間のリンクはサイドを表します。グラフを使用して、各コースの入学度を保存します。たとえば、graph [i]はコースiとともにコースを格納し、次にinDegreeを使用して各ノードのインディグリーを格納します。次に、キューを使用して最初に次数0のノードを格納し、次にキュー内の値を取り出します。各ノードと関連するエッジのみについて、-1にする必要があり、次に0を再スケーリングする必要があります。キューが空になるまでキューに参加します。

  • 結局、グラフにリングがあり、結果の要素の数がコースの総数と等しくない場合は、結果を空にすることができます。

  • 基本的に、このトピックはトポロジカルソートです。

コード

class Solution { public: vector findOrder(int numCourses, vector& prerequisites) { vector res vector graph(numCourses,vector(0)) vector in(numCourses,0) for(auto a:prerequisites){ graph[a.second].push_back(a.first) ++in[a.first] } queue q for(int i=0i

参照

[LeetCode]コーススケジュールIIコースリスト2