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?
For example:
2, [[1,0]]
There are a total of 2 courses to take. To take course 1 you should have finished course 0. So it is possible.
2, [[1,0],[0,1]]
There are a total of 2 courses to take. To take course 1 you should have finished course 0, and to take course 0 you should also have finished course 1. So it is impossible.
bfs1
class Solution {
public:
bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
vector<vector<int> > graph(numCourses, vector<int>(0));
vector<int> in(numCourses, 0);
for (auto a : prerequisites) {
graph[a[1]].push_back(a[0]);
++in[a[0]];
}
queue<int> q;
for (int i = 0; i < numCourses; ++i) {
if (in[i] == 0) q.push(i);
}
while (!q.empty()) {
int t = q.front();
q.pop();
for (auto a : graph[t]) {
--in[a];
if (in[a] == 0) q.push(a);
}
}
for (int i = 0; i < numCourses; ++i) {
if (in[i] != 0) return false;
}
return true;
}
};
Kahn’s algorithm
class Solution {
public:
bool canFinish(int numCourses, vector<pair<int, int>>& prerequisites) {
vector<vector<int>> graph(numCourses, vector<int>(0));
vector<int> inDegree(numCourses, 0);
for(auto prerequisite : prerequisites) {
graph[prerequisite.second].push_back(prerequisite.first);
++inDegree[prerequisite.first];
}
int count = 0;
queue<int> courses;
for (int i = 0; i < numCourses; ++i) {
if (inDegree[i] == 0) courses.push(i);
}
while(!courses.empty()) {
int currentCourse = courses.front();
courses.pop();
for(auto neighbour: graph[currentCourse]){
--inDegree[neighbour];
if(inDegree[neighbour] == 0) courses.push(neighbour);
}
count++;
}
if(count != numCourses) {
return false;
} else {
return true;
}
}
};
dfs
class Solution {
public:
bool canFinish(int numCourses, vector<pair<int, int>>& prerequisites) {
vector<vector<int>> graph(numCourses, vector<int>(0));
vector<int> visit(numCourses, 0);
for(auto prerequisite : prerequisites) {
graph[prerequisite.second].push_back(prerequisite.first);
}
for (int i = 0; i < numCourses; ++i) {
if (visit[i] == 1) continue;
if (!canFinishDFS(graph, visit, i)) return false;
}
return true;
}
bool canFinishDFS(vector<vector<int> > &graph, vector<int> &visit, int i) {
if (visit[i] == -1) return false;
visit[i] = -1;
for (auto a : graph[i]) {
if (!canFinishDFS(graph, visit, a)) return false;
}
visit[i] = 1;
return true;
}
};