There are a total of numCourses courses you have to take. The courses are labeled from 0 to numCourses - 1. You are also given a prerequisites array, where prerequisites[i] = [a[i], b[i]] indicates that you must take course b[i] first if you want to take the course a[i]. For example, the pair [ 1 , 0 ] [1,0] indicates that to take course 1 1 , y…

course-schedule.js

export function canFinish(numCourses, prerequisites) {
  const adjList = {};

  // initialize the adj list
  for (let i = 0; i < numCourses; ++i) {
    adjList[i] = [];
  }

  // build the adj list from prereq, where each prereq is a pair [to, from]
  // where from is a course that must be taken before course to
  for (let i = 0; i < prerequisites.length; ++i) {
    const [to, from] = prerequisites[i];
    adjList[from].push(to);
  }

  // map of visited vertices, where false means the value was seen
  // and true means the value was seen in the current path,
  // and true indicates there is a cycle
  const visited = {};

  function dfs(v) {
    // if the vertex is recorded in the map,
    // return map value
    if (visited[v] != null) {
      return visited[v];
    }

    // mark vertex as being seen the current path
    visited[v] = true;

    const children = adjList[v];
    for (let i = 0; i < children.length; ++i) {
      const child = children[i];
      if (dfs(child)) {
        // if a vertex has been seen twice in the current path,
        // return true indicating a cycle
        return true;
      }
    }

    // mark vertex as seen
    visited[v] = false;
  }

  const vertices = Object.keys(adjList);

  // start dfs from each vertex
  for (let i = 0; i < vertices.length; ++i) {
    if (dfs(vertices[i])) {
      // if dfs returns true, it means there is a cycle
      // which means we cannot complete all courses
      return false;
    }
  }

  // if cycle was not found, we can complete all courses
  return true;
}

// tc: O(V+E)
// sc: O(V+E)