#P4068. 课程表
-
ID: 2309
Tried: 68
Accepted: 27
Difficulty: 4
课程表
题目内容
你这个学期必须选修 numCourses 门课程，记为 0到 numCourses−1 。
在选修某些课程之前需要一些先修课程。 先修课程按数组 prerequisites 给出，其中 prerequisites[i]=[ai,bi] ，表示如果要学习课程 ai则 必须 先学习课程 bi 。
- 例如，先修课程对 [0,1] 表示：想要学习课程 0，你需要先完成课程 1 。
请你判断是否可能完成所有课程的学习？如果可以，返回 true ；否则，返回 false 。
输入描述
- 第一行输入一个整数 numCourses，表示课程总数。
- 第二行输入一个整数 m，表示先修课程对的数量。
- 接下来 m 行，每行输入两个整数 aibi，表示课程 ai 需要先修 bi。
输出描述
如果可以完成所有课程的学习，输出 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<=ai,bi<numCourses
- prerequisites[i]中的所有课程对互不相同
课程表
题解思路
拓扑排序（Kahn 算法，BFS）
适用场景：判断有向图是否有环。
算法步骤：
- 构建有向图：用 邻接表 记录课程的先修关系，用 入度数组 记录每门课程的前置课程数量。
- 拓扑排序：
- 先找到所有 入度为 0 的课程（可以直接学习的课程）。
- 逐步学习这些课程，并更新它们指向的课程的 入度。
- 如果最终所有课程都能学习，则返回
true；否则返回false（存在循环依赖）。
时间复杂度：
- 构建图：O(m)，其中
m为prerequisites的长度。 - 拓扑排序：O(numCourses+m)。
- 总体复杂度：O(numCourses+m)。
代码实现
Python 代码
import sys
from collections import deque
def canFinish(numCourses, prerequisites):
# 构建邻接表和入度表
graph = [[] for _ in range(numCourses)]
in_degree = [0] * numCourses
for a, b in prerequisites:
graph[b].append(a)
in_degree[a] += 1
# 找到所有入度为 0 的课程
queue = deque([i for i in range(numCourses) if in_degree[i] == 0])
count = 0 # 记录已修课程数
while queue:
course = queue.popleft()
count += 1 # 学习一门课程
for next_course in graph[course]:
in_degree[next_course] -= 1
if in_degree[next_course] == 0:
queue.append(next_course)
return count == numCourses
# 读取输入
numCourses = int(sys.stdin.readline().strip())
m = int(sys.stdin.readline().strip())
prerequisites = [list(map(int, sys.stdin.readline().split())) for _ in range(m)]
# 输出结果
print(canFinish(numCourses,prerequisites))
C++ 代码
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
vector<vector<int>> graph(numCourses);
vector<int> in_degree(numCourses, 0);
for (auto& pre : prerequisites) {
graph[pre[1]].push_back(pre[0]);
in_degree[pre[0]]++;
}
queue<int> q;
for (int i = 0; i < numCourses; i++) {
if (in_degree[i] == 0) q.push(i);
}
int count = 0;
while (!q.empty()) {
int course = q.front();
q.pop();
count++;
for (int next : graph[course]) {
if (--in_degree[next] == 0) q.push(next);
}
}
return count == numCourses;
}
int main() {
int numCourses, m;
cin >> numCourses >> m;
vector<vector<int>> prerequisites(m, vector<int>(2));
for (int i = 0; i < m; i++) {
cin >> prerequisites[i][0] >> prerequisites[i][1];
}
cout << (canFinish(numCourses, prerequisites) ? "true" : "false") << endl;
return 0;
}
Java 代码
import java.util.*;
public class Main {
public static boolean canFinish(int numCourses, int[][] prerequisites) {
List<List<Integer>> graph = new ArrayList<>();
int[] inDegree = new int[numCourses];
for (int i = 0; i < numCourses; i++) {
graph.add(new ArrayList<>());
}
for (int[] pre : prerequisites) {
graph.get(pre[1]).add(pre[0]);
inDegree[pre[0]]++;
}
Queue<Integer> queue = new LinkedList<>();
for (int i = 0; i < numCourses; i++) {
if (inDegree[i] == 0) {
queue.offer(i);
}
}
int count = 0;
while (!queue.isEmpty()) {
int course = queue.poll();
count++;
for (int next : graph.get(course)) {
if (--inDegree[next] == 0) {
queue.offer(next);
}
}
}
return count == numCourses;
}
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int numCourses = scanner.nextInt();
int m = scanner.nextInt();
int[][] prerequisites = new int[m][2];
for (int i = 0; i < m; i++) {
prerequisites[i][0] = scanner.nextInt();
prerequisites[i][1] = scanner.nextInt();
}
System.out.println(canFinish(numCourses, prerequisites) ? "true" : "false");
}
}