Leetcode 207. Course Schedule
2017-05-14 本文已影响0人
刘宇轩Freeman
bool canFinish(int numCourses, vector<pair<int, int>>& prerequisites) {
vector<vector<int>> matrix(numCourses,vector<int>(numCourses,0));
vector<int> inDegree(numCourses);
for(int i = 0;i < prerequisites.size();i++){
int pre = prerequisites[i].second;
int ready = prerequisites[i].first;
if(matrix[pre][ready] == 0){
inDegree[ready]++;
matrix[pre][ready] ++;
}
}
int count = 0;
queue<int> queue;
for(int i = 0;i < inDegree.size();i++){
if(inDegree[i] == 0){
queue.push(i);
}
}
while(!queue.empty()){
int course = queue.front();
queue.pop();
count ++;
for(int i = 0;i < numCourses;i++){
if(matrix[course][i] != 0){
if(--inDegree[i] == 0){
queue.push(i);
}
}
}
}
return count == numCourses;
}