当前位置： 面试刷题>> 课程表Ⅱ (经典算法题500道)
### 题目描述补充
题目：**课程表Ⅱ**
在一个大学里，有N门不同的课程，编号从1到N。一些课程之间可能有直接的先修关系，即为了学习课程A，必须先完成课程B。现在给你一个二维数组`numCourses`和一个二维数组`prerequisites`，其中`numCourses`是一个整数，表示课程总数；`prerequisites`中的每一个元素是一对课程对`[a, b]`，表示在学习课程a之前必须先完成课程b。
现在你想知道，为了学习完所有的课程，你至少需要安排多少门课程作为首批课程。首批课程指的是在没有任何先修课程要求的情况下可以直接学习的课程。
请实现一个函数来计算并返回至少需要安排的首批课程数量。
### 示例
**示例 1**:
```
输入: numCourses = 2, prerequisites = [[1,0]]
输出: 1
解释: 总共有2门课程。要学习课程1，你必须先完成课程0。所以你应该先安排课程0，然后安排课程1。
```
**示例 2**:
```
输入: numCourses = 4, prerequisites = [[1,0],[2,0],[3,1],[3,2]]
输出: 2
解释: 总共有4门课程。要学习课程3，你必须先完成课程1和课程2；并且课程1和课程2都必须先完成课程0。
所以一种可能的安排是：首先安排课程0，然后安排课程1和课程2，最后安排课程3。
```
### 解答
这个问题可以通过图的入度（in-degree）来解决。对于每门课程，如果它是其他课程的先修课程，则它的入度会增加。首批课程即为入度为0的课程。
#### PHP 示例代码
```php
function findNumCourses($numCourses, $prerequisites) {
// 构建入度数组
$inDegrees = array_fill(0, $numCourses, 0);
// 构建邻接表
$adjList = array_fill(0, $numCourses, []);
// 初始化入度和邻接表
foreach ($prerequisites as $pair) {
$course = $pair[0];
$prerequisite = $pair[1];
$inDegrees[$course]++;
$adjList[$prerequisite][] = $course;
}
// 使用队列找到所有入度为0的节点
$queue = new SplQueue();
for ($i = 0; $i < $numCourses; $i++) {
if ($inDegrees[$i] == 0) {
$queue->enqueue($i);
}
}
$count = 0;
while (!$queue->isEmpty()) {
$course = $queue->dequeue();
$count++;
foreach ($adjList[$course] as $nextCourse) {
$inDegrees[$nextCourse]--;
if ($inDegrees[$nextCourse] == 0) {
$queue->enqueue($nextCourse);
}
}
}
return $count;
}
```
#### Python 示例代码
```python
from collections import deque
def findNumCourses(numCourses, prerequisites):
inDegrees = [0] * numCourses
adjList = [[] for _ in range(numCourses)]
for course, prereq in prerequisites:
inDegrees[course] += 1
adjList[prereq].append(course)
queue = deque([i for i in range(numCourses) if inDegrees[i] == 0])
count = 0
while queue:
course = queue.popleft()
count += 1
for nextCourse in adjList[course]:
inDegrees[nextCourse] -= 1
if inDegrees[nextCourse] == 0:
queue.append(nextCourse)
return count
```
#### JavaScript 示例代码
```javascript
function findNumCourses(numCourses, prerequisites) {
const inDegrees = new Array(numCourses).fill(0);
const adjList = new Array(numCourses).fill(0).map(() => []);
for (const [course, prereq] of prerequisites) {
inDegrees[course]++;
adjList[prereq].push(course);
}
const queue = [];
for (let i = 0; i < numCourses; i++) {
if (inDegrees[i] === 0) {
queue.push(i);
}
}
let count = 0;
while (queue.length > 0) {
const course = queue.shift();
count++;
for (const nextCourse of adjList[course]) {
inDegrees[nextCourse]--;
if (inDegrees[nextCourse] === 0) {
queue.push(nextCourse);
}
}
}
return count;
}
```
这些代码示例都使用了图的入度来找出首批可以学习的课程数量，使用了广度优先搜索（BFS）的方法遍历图。码小课网站中有更多相关内容分享给大家学习。