Description
There are a total of n courses you have to take, labeled from 0 to n-1.
Some courses may have prerequisites, for example to take course 0 you have to first take course 1, which is expressed as a pair: [0,1]
Given the total number of courses and a list of prerequisite pairs, is it possible for you to finish all courses?
Answer
Using BFS to solve the problem. Find classes which do not have prerequisites and push those into queue. Traverse the queue and pop out the front element. The front element represents the course to be taken next.
Using a vector to count how many prerequisites each courses have and another vector of unordered_multiset to record which courses are prerequisites of each course.
Code
C++
class Solution {
public:
bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
if(prerequisites.size() == 0 || numCourses <= 1) return true;
int n = prerequisites.size();
vector<int> indegree(numCourses, 0);
vector<unordered_multiset<int>> edges(numCourses);
for(int i = 0; i < n; ++i)
{
edges[prerequisites[i][1]].insert(prerequisites[i][0]);
indegree[prerequisites[i][0]]++;
}
queue<int> q;
for(int i = 0; i < numCourses; ++i)
if(indegree[i] == 0) q.push(i);
int node = 0;
while(!q.empty())
{
int cur = q.front();
q.pop();
++node;
for(auto it = edges[cur].begin(); it != edges[cur].end(); ++it)
{
--indegree[*it];
if(indegree[*it] == 0) q.push(*it);
}
}
return node == numCourses;
}
};
