題目： 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;
    }
};