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.
def canFinish(numCourses, prerequisites):
graph = [[] for _ in range(numCourses)]; visited = [0] * numCourses; for x, y in prerequisites:
graph[x].append(y);
def dfs(i):
if visited[i] == -1:
return False; if visited[i] == 1:
return True; visited[i] = -1; for j in graph[i]:
if not dfs(j):
return False; visited[i] = 1; return True; for i in range(numCourses):
if not dfs(i):
return False; return TrueFollow-up:
What if we want to find the order in which we should take the courses?
