我們可以用 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;
}
};