207. Course Schedule

Difficulty:
Related Topics:
Similar Questions:

Problem

There are a total of n courses you have to take, labeled from 0 to n-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: 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.

Example 2:

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.

Note:

Solution

/**
 * @param {number} numCourses
 * @param {number[][]} prerequisites
 * @return {boolean}
 */
var canFinish = function(numCourses, prerequisites) {
  var edges = Array(numCourses).fill(0).map(_ => Array(numCourses).fill(0));
  var incoming = Array(numCourses).fill(0);
  var len = prerequisites.length;
  var post = 0;
  var prev = 0;
  var queue = [];
  var num = 0;
  var count = 0;

  for (var i = 0; i < len; i++) {
    prev = prerequisites[i][1];
    post = prerequisites[i][0];
    if (edges[prev][post] === 0) {
      incoming[post]++;
      edges[prev][post] = 1;
    }
  }

  for (var j = 0; j < numCourses; j++) {
    if (incoming[j] === 0) queue.push(j);
  }

  while (queue.length) {
    count++;
    num = queue.pop()
    for (var k = 0; k < numCourses; k++) {
      if (edges[num][k] === 1 && --incoming[k] === 0) queue.push(k);
    }
  }

  return count === numCourses;
};

Explain:

nope.

Complexity: