Course Schedule

Description

There are a total of numCourses courses you have to take, labeled from 0 to numCourses-1.

Some courses may have prerequisites, for example to take course 0 you have to first take course 1, which is expressed as a pair: [0,1]

Given the total number of courses and a list of prerequisite pairs, is it possible for you to finish all courses?

 

Example 1:

Input: numCourses = 2, prerequisites = [[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.

Example 2:

Input: numCourses = 2, prerequisites = [[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.

 

Constraints:

• The input prerequisites is a graph represented by a list of edges, not adjacency matrices. Read more about how a graph is represented.
• You may assume that there are no duplicate edges in the input prerequisites.
• 1 <= numCourses <= 10^5

Solution(javascript)

/*
 * @lc app=leetcode id=207 lang=javascript
 *
 * [207] Course Schedule
 */

// @lc code=start
/** Cycle Detection/Topological Sort
 * @param {number} numCourses
 * @param {number[][]} prerequisites
 * @return {boolean}
 */
const canFinish = function (numCourses, prerequisites) {
  const adjList = prerequisites.reduce((acc, [a, b]) => {
    acc[a] = acc[a] || []
    acc[a].push(b)
    return acc
  }, [])
  const start = []
  const end = []
  const hasCycle = (course) => {
    if (end[course]) {
      return false
    }
    if (start[course]) {
      return true
    }
    start[course] = true
    if ((adjList[course] || []).some(next => hasCycle(next))) {
      return true
    }
    end[course] = true
    return false
  }
  for (let i = 0; i < numCourses; i++) {
    if (hasCycle(i, [])) {
      return false
    }
  }
  return true
}