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.
public boolean canFinish(int numCourses, int[][] prerequisites) {
int[][] graph = new int[numCourses][];
int[] visited = new int[numCourses];
for (int[] pair : prerequisites) {
graph[pair[0]] = Arrays.copyOf(graph[pair[0]], graph[pair[0]].length + 1);
graph[pair[0]][graph[pair[0]].length - 1] = pair[1];
}
for (int i = 0;
i < numCourses;
i++) {
if (!dfs(graph, visited, i)) {
return false;
}
}
return true;
}
private boolean dfs(int[][] graph, int[] visited, int i) {
if (visited[i] == -1) {
return false;
}
if (visited[i] == 1) {
return true;
}
visited[i] = -1;
for (int j : graph[i]) {
if (!dfs(graph, visited, j)) {
return false;
}
}
visited[i] = 1;
return true;
}Follow-up:
What if we want to find the order in which we should take the courses?
