# 210 - Course Schedule II

解法一 - Topological Sort

這題的解法跟 207 基本上一樣，差別只在於回傳的東西不同，實作如下：

class Solution {
public:
    vector<int> findOrder(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 parent = prerequisites[i][1];
            int child = prerequisites[i][0];

            ++inDegree[child];
            graph[parent].push_back(child);
        }

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

        // Find the topological ordered courses
        vector<int> ordered;
        while(!sources.empty()) {
            int course = sources.front();
            sources.pop();

            ordered.push_back(course);

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

        return ordered.size() == numCourses ? ordered : vector<int>{};
    }
};