题目直达链接

1. 题目描述

你这个学期必须选修 numCourses 门课程，记为 0 到 numCourses - 1 。

在选修某些课程之前需要一些先修课程。 先修课程按数组 prerequisites 给出，其中 prerequisites[i] = [ai, bi] ，表示如果要学习课程 ai 则 必须 先学习课程  bi 。

• 例如，先修课程对 [0, 1] 表示：想要学习课程 0 ，你需要先完成课程 1 。

请你判断是否可能完成所有课程的学习？如果可以，返回 true ；否则，返回 false 。

示例 1：

输入：numCourses = 2, prerequisites = [[1,0]]

输出：true

解释：总共有 2 门课程。学习课程 1 之前，你需要完成课程 0 。这是可能的。

示例 2:

输入：numCourses = 2, prerequisites = [[1,0],[0,1]]

输出：false

解释：总共有 2 门课程。学习课程 1 之前，你需要先完成​课程 0 ；并且学习课程 0 之前，你还应先完成课程 1 。这是不可能的。

提示：

• 1 <= numCourses <= 2000

• 0 <= prerequisites.length <= 5000

• prerequisites[i].length == 2

• 0 <= ai, bi < numCourses

• prerequisites[i] 中的所有课程对 互不相同

2. 分析

核心思路：建图，广度优先搜索

1. 建图，维护节点入度

2. 广搜，从节点入度为0的课程(没有前置依赖)开始搜索，并更新其依赖的下游节点入度，将新的入度为0节点继续搜索，反复

3. 结果：无法再继续搜索时，返回搜索的课程数是否等于numCources

3. 代码

func canFinish(numCourses int, prerequisites [][]int) bool {
    /*
        1. 建图
            a. degree[i] 表示节点i的入度
            b. to[i][] 表示i的后置依赖
    */
    degrees := make([]int, numCourses)
    to := make([][]int, numCourses)
    for _, prerequisted := range prerequisites {
        // 学习a之前需要学习b a的前置依赖是b  b->a
        a, b := prerequisted[0], prerequisted[1]
        // 更新b的依赖节点
        to[b] = append(to[b], a)
        // 更新a的入度
        degrees[a]++
    }
    // 2. 从入度为0的节点开始，广度搜索，并统计搜索数
    q := list.New()
    for node, degree := range degrees {
        if degree == 0 {
            q.PushBack(node)
        }
    }
    visited := 0
    for q.Len() > 0 {
        visited++
        node := q.Remove(q.Front()).(int)
        for _, target := range to[node] {
            // 减少访问，更新入度
            degrees[target]--
            if degrees[target] == 0 {
                q.PushBack(target)
            }
        }
    }
    // 3. 返回是否访问完所有节点
    return visited == numCourses
}