课程表

题解思路

拓扑排序（Kahn 算法，BFS）

适用场景：判断有向图是否有环。

算法步骤：

1. 构建有向图：用 邻接表 记录课程的先修关系，用 入度数组 记录每门课程的前置课程数量。
2. 拓扑排序：

Leetcode 53.课程表-原题链接

题目内容

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

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

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

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

输入描述

• 第一行输入一个整数 $numCourses$，表示课程总数。
• 第二行输入一个整数 $m$，表示先修课程对的数量。
• 接下来 $m$ 行，每行输入两个整数 $a_i b_i$，表示课程 $a_i$ 需要先修 $b_i$。

输出描述

如果可以完成所有课程的学习，输出 true，否则输出 false。

样例1

输入

2
1
1 0

输出

true

说明

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

样例2

输入

2
2
1 0
0 1

输出

false

说明

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

提示

• $1 <= numCourses <= 2000$
• $0 <= prerequisites.length <= 5000$
• $prerequisites[i].length == 2$
• $0 <= a_i, b_i < numCourses$
• $prerequisites[i]$中的所有课程对互不相同