Fb

LeetCode：210。コーススケジュールII



Leetcode 210 Course Schedule Ii



トピックの説明

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

一部のコースには、たとえばコースを受講するための前提条件がある場合があります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. 入力の前提条件に重複するエッジがないと想定する場合があります。

問題解決

同じ LeetCode：207。コーススケジュール 。解決プロセスを記録する必要があり、解決プロセスのシーケンスが求められるシーケンスです。

ACコード

class Solution { public: vector<int> findOrder(int numCourses, vector<pair<int, int>>& prerequisites) { unordered_set<int> travelVertices multimap<int, int> adjVer // adjacency matrix bool hasNewVer = true vector<int> order for(auto iter = prerequisites.begin() iter != prerequisites.end() ++iter) { adjVer.insert({iter->first, iter->second}) } while(travelVertices.size() != numCourses && hasNewVer) { // Record the entry level of each course vector<int> courses(numCourses, 0) for(size_t i = 0 i < numCourses ++i) { for(auto iter = adjVer.find(i) iter != adjVer.end() && iter->first == i ++iter) { if(travelVertices.find(iter->second) == travelVertices.end()) { ++courses[iter->first] } } } hasNewVer = false for(size_t i = 0 i < courses.size() ++i) { // Courses with a degree of 0 can be if(courses[i] == 0 && travelVertices.find(i) == travelVertices.end()) { travelVertices.insert(i) order.push_back(i) hasNewVer = true } } } if(travelVertices.size() != numCourses) { return {} } else { return order } } }