I. Title Description:

Leetcode-cn.com/problems/co… Now you have a total of n classes you need to take, zero to n minus one.

Some prerequisite courses are required before you can take certain courses. For example, to take course 0, you need to complete course 1 first. We represent them with a match: [0,1]

Given the number of courses and their prerequisites, return the order in which you studied all the courses in order to complete them.

There could be multiple correct orders, and you just have to return one. If it is not possible to complete all lessons, return an empty array.

**** Example 1:

Input: 2, [[1,0]] output: [0,1] explanation: there are 2 courses in total. To take course 1, you need to complete course 0 first. Therefore, the correct course order is [0,1].Copy the code

Ii. Analysis of Ideas:

  • A topological sort
  • Create a graph and record the degree of entry at each point
  • The point with zero entry degree is put into the queue, and the entry degree of the point connected to the point is reduced by 1 at the same time. If another point with zero entry degree is found, the point is put into the queue. A path array is also maintained to record the queue order

Iii. AC Code:

/ * * *@param {number} numCourses
 * @param {number[][]} prerequisites
 * @return {number[]}* /
var findOrder = function (numCourses, prerequisites) {
    const path = []
    const graph = new Array(numCourses).fill(null).map(_= > new Set())
    const indegre = new Array(numCourses).fill(0)
    for (let i = 0; i < prerequisites.length; i++) {
        const [W, V] = prerequisites[i]
        graph[V].add(W)
        indegre[W]++
    }
    const quene = []
    for (let i = 0; i < indegre.length; i++) {
        if (indegre[i] === 0) {
            quene.unshift(i)
        }
    }
    while (quene.length) {
        const V = quene.pop()
        path.push(V)
        graph[V].forEach(W= > {
            indegre[W]--
            if (indegre[W] === 0) {
                quene.unshift(W)
            }
        })
    }
    return path.length === numCourses ? path : []
};

Copy the code