# 207 - Course Schedule

解法一 - Topological Sort

我們可以用 adjacency list 來表示 graph，另外儲存一個 inDegree 來表示有多少個 edge 指向這個 node。每次我們只要找到 inDegree 是 0 的 node（也就是 source），移除這個 node，並更新這個 node 所有 child 的 inDegree 就可以繼續找下一個 node。

class Solution {
public:
    bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
        // Init the graph
        unordered_map<int, int> inDegree;
        unordered_map<int, vector<int>> graph;
        for(int i = 0; i < numCourses; ++i) {
            inDegree[i] = 0;
            graph[i] = {};
        }

        // Build the graph
        for(int i = 0; i < prerequisites.size(); ++i) {
            int prereq = prerequisites[i][1];
            int course = prerequisites[i][0];

            graph[prereq].push_back(course);
            ++inDegree[course];
        }

        // Find all sources
        queue<int> sources;
        for(auto& p: inDegree) {
            if(p.second == 0) {
                sources.push(p.first);
            }
        }

        // Build the sorted order
        vector<int> sortedCourse;
        while(!sources.empty()) {
            int course = sources.front();
            sources.pop();

            sortedCourse.push_back(course);

            for(auto& child: graph[course]) {
                if(--inDegree[child] == 0) {
                    sources.push(child);
                }
            }
        }

        // If the size of topological order list is not equal to numCourses
        // Return false
        return sortedCourse.size() == numCourses;
    }
};