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:
- 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.
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:
- Time complexity : O(n^2).
- Space complexity : O(n^2).