207. 课程表
4 min
题目
解法：拓扑排序
思路
核心思想是使用拓扑排序（Kahn算法）检测有向图中的环。该方法通过不断移除入度为0的节点来判断图是否无环。其正确性基于：若图中存在环，则环内节点的入度永远无法降为0，因此无法被加入队列；反之，若所有节点最终都能被处理，则图必然无环。
- Step 1: 构建邻接表和入度数组，记录每门课程的后续课程和先修课程数量
- Step 2: 将所有入度为0的课程（无先修课）加入队列
- Step 3: 循环取出队列中的课程，计数并遍历其后续课程，将对应后续课程的入度减1
- Step 4: 若后续课程入度变为0，则将其加入队列
- Step 5: 最终比较已处理课程数与总课程数，相等则返回true
复杂度
- 时间复杂度: O(n + m)$，其中n为课程数，m为先修关系数。需要遍历所有节点和边各一次。
- 空间复杂度: O(n + m)$，用于存储邻接表和入度数组，以及BFS队列。
代码
class Solution {
public:
bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
vector<vector<int>> adj(numCourses);
vector<int> inDegree(numCourses, 0);
// 构建邻接表和入度数组
for (auto& pre : prerequisites) {
adj[pre[1]].push_back(pre[0]);
inDegree[pre[0]]++;
}
queue<int> q;
// 初始化：将所有入度为 0 的节点加入队列
for (int i = 0; i < numCourses; i++) {
if (inDegree[i] == 0) {
q.push(i);
}
}
int count = 0; // 记录可以完成的课程数
// BFS 拓扑排序
while (!q.empty()) {
int u = q.front();
class Solution {
public:
bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
vector<vector<int>> adj(numCourses);
vector<int> inDegree(numCourses, 0);
// 构建邻接表和入度数组
for (auto& pre : prerequisites) {
adj[pre[1]].push_back(pre[0]);
inDegree[pre[0]]++;
}
queue<int> q;
// 初始化：将所有入度为 0 的节点加入队列
for (int i = 0; i < numCourses; i++) {
if (inDegree[i] == 0) {
q.push(i);
}
}
int count = 0; // 记录可以完成的课程数
// BFS 拓扑排序
while (!q.empty()) {
int u = q.front();
q.pop();
count++;
// 遍历当前节点的邻居
for (int v : adj[u]) {
inDegree[v]--; // 移除依赖
if (inDegree[v] == 0) {
q.push(v);
}
}
}
// 如果可以完成所有课程，则返回 true
return count == numCourses;
}
};