This is the third day of my participation in the First Challenge 2022

The title

207. The curriculum

You must take numCourses this semester, marked 0 to numcourses-1.

Some prerequisite courses are required before you can take certain courses. Prerequisites Prerequisites Prerequisites for system system system 2005: System system for System System 2005: System system for System System 2005: System system for System System 2005: System system for System System 2005: System system for system System 2005

  • For example, advanced placement courses yes[0, 1]Express: Want to learn a course0You need to complete the course first1 。

Would you please judge whether it is possible to complete all the courses? If so, return true; Otherwise, return false.

 

Example 1:

Input: numCourses = 2, resident = [[1,0]] output: true Before you can study course 1, you need to complete course 0. It's possible.Copy the code

Example 2:

Input: numCourses = 2, prerequisites = [[1,0],[0,1]] You need to complete Course 0 before taking course 1; And you should also complete course 1 before taking course 0. It's impossible.Copy the code

 

Tip:

  • 1 <= numCourses <= 105
  • 0 <= prerequisites.length <= 5000
  • prerequisites[i].length == 2
  • 0 <= ai, bi < numCourses
  • prerequisites[i]All the courses in theEach other is not the same

Train of thought

  1. This topic uses a knowledge point called topological sorting, which basically means that we start with each position as a node, and then we connect the related nodes to each other, and finally we determine whether the connection is closed loop;
  2. In this case, we use a directed connection graph to make the connection because the relationship is dependent on the other one and cannot be reversed.
  3. Then talk about the difference between topological sorting and ordinary tree structure. The tree structure only has one root node per node and can have multiple child nodes, while the topological sorting diagram is that each node can have multiple root nodes and multiple child nodes.
  4. So once we get to the concept let’s talk about how to implement it, we can use one, rightlistArray, to record how many preconditions each node has, each time one condition is satisfied inlistThe corresponding position in the array is subtracted by one when the node’s preconditions are0“Indicates that the task can be completed directly.
  5. One moremapFor example, course A depends on course B, so we need to record it on course B, and when it completes, we need to notify Course A that it is ready to execute;
  6. And then we usedoneListTo keep track of completed lists, not to count how many completed, how many completed we useresultTo keep track of the number,doneListThe main function is to send notification, tellmapThe node that depends on it says, I’m done, you can go ahead;
  7. mapAfter each node is notified in thelistThe number of preconditions should be reduced by one, and the current condition is0“, it’s ready to go, add itdoneListIn, go to queue up at the entrance of the village to inform small friends with broadcast, and complete the number at the same timeresultGal.;
  8. Finally, we’re done, and we judge a done numberresultWhether is equal to thenumCoursesCan.

implementation

/ * * *@param {number} numCourses
 * @param {number[][]} prerequisites
 * @return {boolean}* /
var canFinish = function(numCourses, prerequisites) {
    let list = new Array(numCourses).fill(0);
    let map = new Map(a);// Set up the mapping through the list of relationships
    for (let i = 0; i < prerequisites.length; i++) {
        const [ a, b ] = prerequisites[i];
        list[a]++;
        // Who to notify about changes
        map.set(b, (map.get(b) || []).concat([ a ]));
    }

    // Complete the list without preconditions at the beginning
    let doneList = [];
    for (let i = 0; i < list.length; i++) {
        if (list[i] === 0) { doneList.push(i); }}// Keep track of how many entries are completed
    let result = doneList.length;

    // Take them out one by one to tell your friends that YOU are done
    while (doneList.length) {
        // breadth-first search
        const cur = doneList.shift();
        const teamList = map.get(cur) || [];

        // For all dependent partners, the precondition is reduced by one. If the precondition is 0, it is complete
        for (let i = 0; i < teamList.length; i++) {
            list[teamList[i]]--;

            // Wait in line at the entrance of the village, waiting for the announcement of friends
            if (list[teamList[i]] === 0) { doneList.push(teamList[i]); result++; }}}return result === numCourses;
};
Copy the code

If you understand it, you can click on it and see you in the next topic. If there is no accident after the article will be in this form, there are good suggestions welcome to comment area.