題目: LeetCode - 207. Course Schedule
題目說明
給一個整數 numCourses 表示必須要修的課的數量,課程編號 0 ~ numCourses - 1,和一個二維陣列 prerequisites,裡面每個陣列含有兩個課程編號的數字,如 [0, 1] 表修課程 0 前需要先修完課程 1。求符合 prerequisites 的條件下是否能修完所有的課程。
解題思路
Topological Sort 類型的題目,先記錄每堂課需要修多少先修課,並以先修課為 Index 紀錄以此課為先修課的課號。
建立一個 Queue 並將不需要修先修課的課放入,之後一一取出,取出時更新每堂課需要修多少先修課的數量,當遇到需要先修課數量為 0 時將其課放入 Queue 中。
循環結束時表所有能修的課皆已修完,此時檢查若還有課需要修先修課,表有 loop 無法修完所有課。
參考解法
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38
| class Solution { public: bool canFinish(int numCourses, vector<vector<int>>& prerequisites) { map<int, vector<int>> preReq; vector<int> numPreReq(numCourses); for (const auto& v : prerequisites) { ++numPreReq[v[0]]; preReq[v[1]].push_back(v[0]); }
queue<int> courses; for (int i = 0; i < numCourses; ++i) { if (numPreReq[i] == 0) { courses.push(i); } }
while (!courses.empty()) { int cur = courses.front(); courses.pop();
for (const auto& course : preReq[cur]) { --numPreReq[course]; if (!numPreReq[course]) { courses.push(course); } } }
for (int i = 0; i < numCourses; ++i) { if (numPreReq[i]) { return false; } }
return true; } };
|