Course Schedule
There are a total of numCourses courses you have to take, labeled from 0 to numCourses - 1. You are given an array of pairs prerequisites where prerequisites[i] = [ai, bi] indicates that you must take course ai after you take course bi. Return true if it is possible to finish all courses, otherwise return false.
Constraints:
- 1 <= numCourses <= 2000
- 0 <= prerequisites.length <= numCourses * (numCourses - 1) / 2
- prerequisites[i].length == 2
- 0 <= ai, bi < numCourses
- ai != bi
- All the pairs [ai, bi] are distinct.
Examples:
Input: [2, [[1,0]]]
Output: true
Explanation: There are a total of 2 courses to take. To take course 1 you should have finished course 0. So it is possible.
Input: [2, [[1,0],[0,1]]]
Output: false
Explanation: 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.
Solutions
Topological Sorting
We use a topological sorting approach to solve this problem. We create a graph where each course is a node, and the prerequisites are the edges. We then use a depth-first search (DFS) to traverse the graph. If we encounter a cycle, we return false. Otherwise, we return true.
class Solution {
public: bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
vector<vector<int>> graph(numCourses);
vector<int> visited(numCourses, 0);
for (auto& pair : prerequisites) {
graph[pair[0]].push_back(pair[1]);
}
function<bool(int)> dfs = [&](int i) {
if (visited[i] == -1) {
return false;
}
if (visited[i] == 1) {
return true;
}
visited[i] = -1;
for (int j : graph[i]) {
if (!dfs(j)) {
return false;
}
}
visited[i] = 1;
return true;
}
;
for (int i = 0;
i < numCourses;
i++) {
if (!dfs(i)) {
return false;
}
}
return true;
}Follow-up:
What if we want to find the order in which we should take the courses?
