# 207 - Course Schedule

## 解法一 - Topological Sort

``````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;
}
};
``````