Implement the courseSchedulePossible method that checks whether all courses can be completed from the prerequisites.
The input contains the number of courses and a list of prerequisite pairs.
Each pair [course, prerequisite] means the prerequisite course must be completed before taking the course. Your task is to check whether it is possible to complete all courses.
If the prerequisite graph contains a cycle, the courses in that cycle cannot be completed, so return false. Otherwise, return true.
Example 1
2[[1,0]]1trueExample 2
2[[1,0],[0,1]]2falseExample 3
3[[1,0],[2,1]]2trueUse topological sorting with indegrees.
Build a directed graph from prerequisites. For every edge prerequisite -> course, increase the indegree of the course. Courses with indegree 0 can be taken first because they have no pending prerequisites.
Repeatedly remove available courses and reduce the indegree of dependent courses. If all courses can be processed, return true; otherwise, a cycle exists.
Pseudocode:
function courseSchedulePossible(courses, prerequisites, size):
graph = list of empty lists for each course
indegree = array of zeroes with length courses
for each pair in prerequisites:
course = pair[0]
prerequisite = pair[1]
add course to graph[prerequisite]
indegree[course]++
queue = all courses with indegree 0
completed = 0
while queue is not empty:
current = remove front from queue
completed++
for each nextCourse in graph[current]:
indegree[nextCourse]--
if indegree[nextCourse] == 0:
push nextCourse into queue
return completed == courses