“This is the 13th day of my participation in the First Challenge 2022. For details: First Challenge 2022”

[B] [C] [D]

Now you have a total of numCourses to select, denoting 0 to numcourses-1. For example, for example, system member for office system [I] = system member for OFFICE system [AI, bi]

  • For example, want to take a course0You need to complete the course first1, we use a match to represent:[0, 1] 。

Returns the order in which you studied in order to complete all the lessons. There could be multiple correct orders, and you just have to return any one of them. If it is not possible to complete all lessons, return an empty array.

Example 1:

Input: numCourses = 2, resident = [[1,0]] output: [0,1] To take course 1, you need to complete course 0 first. Therefore, the correct course order is [0,1].Copy the code

Example 2:

Input: numCourses = 4, resident = [[1,0],[2,0],[3,1]] To take course 3, you should complete course 1 and Course 2 first. And both course 1 and course 2 should come after course 0. Therefore, a correct order of lessons is [0,1,2,3]. Another correct order is [0,2,1,3].Copy the code

Example 3:

Input: numCourses = 1, Resident = [] output: [0]Copy the code

 

Tip:

  • 1 <= numCourses <= 2000
  • 0 <= prerequisites.length <= numCourses * (numCourses - 1)
  • prerequisites[i].length == 2
  • 0 <= ai, bi < numCourses
  • ai ! = bi
  • all[ai, bi] Each other is not the same

Their thinking

In this case, we can abstract the relationship between courses as a graph, each course has a number of elective courses, the degree is several. So not depend on the courses of course into the degree is 0, we should learn the degrees of 0 course, when the lessons learned, need to rely on its course into 1, so that when a course learned all the courses, it’s into the degree becomes 0, this figure is in fact the process of topological sort. If you don’t know anything about topological sorting, you can read my previous do you really know anything about sorting? This article, we will not repeat here. And pairs of courses that have each other’s prerequisites will form loops in the graph that can’t go to zero, so topological sorting can’t handle them. Therefore, we can abstract the course relations in this question into a graph for topological sorting, and the process of topological sorting is the process of learning courses. When the topological sorting is complete, the sorting result array holds a possible sequence of lessons we can learn. If the length of the array is equal to numCourses, the sorted array can be returned. If the length is equal to numCourses, the sorted array can be returned. Otherwise, the sorted array can be returned.

The demo

Code implementation

var findOrder = function (numCourses, Const nums = Array(numCourses).fill(0), Map = Array(numCourses) for (let I = 0; i < prerequisites.length; I ++) {const [a, b] = Resident [I] nums[a]++ if (map[b]) map[b]. Push (a) else map[b] = [a]} Queue = [] const res = [], // Queue = [] // queue = [] i < numCourses; I ++) {if (nums[I] === 0) queue.push(I)} while (queue.length) {const cur = queue.shift(), List = map[cur]; Res.push (cur) if (list) {for (let I = 0; i < list.length; If (nums[list[I]] === 0) queue.push(list[I])}}} if (nums[list[I]] === 0) queue. Return the order in which lessons were learned, otherwise return an empty array return res.length === numCourses? res : [] }Copy the code

At this point we are done with Leetcode-210-Schedule II

If you have any questions or suggestions, please leave a comment! 👏 🏻 👏 🏻 👏 🏻