# 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>{};
}
};
Last updated