课程表 leecode207

package main

import "fmt"

//你这个学期必须选修 numCourse 门课程，记为 0 到 numCourse-1 。
//
//在选修某些课程之前需要一些先修课程。 例如，想要学习课程 0 ，你需要先完成课程 1 ，我们用一个匹配来表示他们：[0,1]
//
//给定课程总量以及它们的先决条件，请你判断是否可能完成所有课程的学习？
//
// 
//
//示例 1:
//
//输入: 2, [[1,0]]
//输出: true
//解释: 总共有 2 门课程。学习课程 1 之前，你需要完成课程 0。所以这是可能的。
//示例 2:
//
//输入: 2, [[1,0],[0,1]]
//输出: false
//解释: 总共有 2 门课程。学习课程 1 之前，你需要先完成​课程 0；并且学习课程 0 之前，你还应先完成课程 1。这是不可能的。
// 
func main() {
    fmt.Println(canFinish(2,[][]int{{0,1}}))
}
func canFinish(numCourses int, prerequisites [][]int) bool {
    learnCount := 0
    learn := make([]int, 0)
    learnMap := make(map[int]int)
    learnChangeMap := make(map[int][]int)
    for _, prerequisite := range prerequisites {
        if len(prerequisite) < 2 {
            continue
        }
        learnMap[prerequisite[1]]++
        if learnChangeMap[prerequisite[0]] == nil {
            learnChangeMap[prerequisite[0]] = make([]int, 0)
        }
        learnChangeMap[prerequisite[0]] = append(learnChangeMap[prerequisite[0]], prerequisite[1])
    }
    for i := 0; i < numCourses; i++ {
        if learnMap[i] == 0 {
            learn = append(learn, i)
            learnCount++
        }
    }
    for len(learn) > 0 {
        nowLearn := learn[0]
        learn = learn[1:]
        changeInfo := learnChangeMap[nowLearn]
        for _, info := range changeInfo {
            learnMap[info] --
            if learnMap[info] == 0 {
                learn = append(learn, info)
                learnCount++
            }
        }
    }
    return learnCount >= numCourses
}