October 27, 2021: curriculum. You must take numcourses this semester

2021-10-27： The curriculum . You must take this semester numCourses Courses , Write it down as 0 To numCourses - 1 . Before you take some courses, you need some prerequisite courses . Prerequisite courses by array prerequisites give , among prerequisitesi = ai, bi , If you want to learn a course ai be must Learn the course first bi . for example , The prerequisite course is right for 0, 1 Express ： Want to learn the course 0 , You need to finish the course first 1 . Please judge whether it is possible to complete all the courses ？ If possible , return true ; otherwise , return false . Power button 207.

Fuda answer 2021-10-27：

A topological sort .

The code to use golang To write . The code is as follows ：

package main

import "fmt"

func main() {
    numCourses := 2
    prerequisites := [][]int{{1, 0}}
    ret := canFinish1(numCourses, prerequisites)
    fmt.Println(ret)
}

//  One node, It's just a course 
// name It's the course number 
// in It's the depth of the course 
type Course struct {
    name  int
    in    int
    nexts []*Course
}

func NewCourse(n int) (res *Course) {
    res = &Course{}
    res.name = n
    res.in = 0
    res.nexts = make([]*Course, 0)
    return
}

func canFinish1(numCourses int, prerequisites [][]int) bool {
    if len(prerequisites) == 0 {
        return true
    }
    //  A number   Corresponding   An example of a class 
    nodes := make(map[int]*Course)
    for _, arr := range prerequisites {
        to := arr[0]
        from := arr[1] // from -> to
        if _, ok := nodes[to]; !ok {
            nodes[to] = NewCourse(to)
        }
        if _, ok := nodes[from]; !ok {
            nodes[from] = NewCourse(from)
        }
        t := nodes[to]
        f := nodes[from]
        f.nexts = append(f.nexts, t)
        t.in++
    }
    needPrerequisiteNums := len(nodes)
    //Queue<Course> zeroInQueue = new LinkedList<>();
    zeroInQueue := make([]*Course, 0)
    for _, node := range nodes {
        if node.in == 0 {
            zeroInQueue = append(zeroInQueue, node)
        }
    }
    count := 0
    for len(zeroInQueue) > 0 {
        //Course cur = zeroInQueue.poll();
        cur := zeroInQueue[len(zeroInQueue)-1]
        zeroInQueue = zeroInQueue[0 : len(zeroInQueue)-1]
        count++
        for _, next := range cur.nexts {
            next.in--
            if next.in == 0 {
                zeroInQueue = append(zeroInQueue, next)
            }
        }
    }
    return count == needPrerequisiteNums
}

The results are as follows ：

picture

---

Zuo Shen java Code