Let’s assume that there are a total of n courses labeled from 0 0 to n−1 . Some courses may have prerequisites. A list of prerequisites is specified such that if Prerequisites i ​ =a,b , you must take course b before course a . Given the total number of courses n and a list of the prerequisite pairs, return the course order a student should take…

course-schedule-2.js

export function findOrder(n, prerequisites) {
  const adjList = {};

  // init adj list
  for (let i = 0; i < n; ++i) {
    adjList[i] = [];
  }

  // build adj list from prereqs
  for (let i = 0; i < prerequisites.length; ++i) {
    const [to, from] = prerequisites[i];
    adjList[from].push(to);
  }

  // vertex: true means this vertex is in the current path
  // it means we found a cycle, we need to stop
  // vertex: false means this vertex has been processed before
  const visited = {};
  const result = [];

  const vertices = Object.keys(adjList);

  // begin post-order dfs from each vertex to build the reversed result array
  for (let i = 0; i < vertices.length; ++i) {
    if (dfs(vertices[i], visited, adjList, result)) {
      return [];
    }
  }

  // reverse the result array to get the correct result
  return result.reverse().map(vertex => parseInt(vertex));
}

function dfs(vertex, visited, adjList, result) {
  // if the vertex is defined in the map,
  // it means it has been seen before
  // it was either successfully processed,
  // or it was seen twice in the same path,
  // meaning a cycle
  if (visited[vertex] != null) {
    return visited[vertex];
  }

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

  const children = adjList[vertex];
  for (let i = 0; i < children.length; ++i) {
    // if any child dfs returns true,
    // it means there is a cycle
    if (dfs(children[i], visited, adjList, result)) {
      return true;
    }
  }

  // add the vertex to the result array
  result.push(vertex);

  // mark vertex as processed
  visited[vertex] = false;
}

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