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.
function canFinish(numCourses, prerequisites) {
let graph = Array.from(
{
length: numCourses,
},
() => []
);
let visited = Array.from(
{
length: numCourses,
},
() => 0
);
for (let [x, y] of prerequisites) {
graph[x].push(y);
}
function dfs(i) {
if (visited[i] === -1) {
return false;
}
if (visited[i] === 1) {
return true;
}
visited[i] = -1;
for (let j of graph[i]) {
if (!dfs(j)) {
return false;
}
}
visited[i] = 1;
return true;
}
for (let 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?
