题目直达链接

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
}