建图 + Kahn 队列删入度为零节点，处理完全部节点即无环。
OJ: leetcodecn
题目 ID: course-schedule
难度:普及+/提高
标签:拓扑排序BFS图cpppython
日期: 2026-07-29 13:10
题意
给定课程数和依赖关系，判断能否完成所有课程。
思路
建依赖图，统计入度，Kahn 算法不断删除入度为 0 的节点。全部处理完则无环。
代码
cpp
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
bool canFinish(int n, vector<vector<int>> &prerequisites) {
vector<vector<int>> g(n);
vector<int> indeg(n);
for (auto &e : prerequisites) {
// 先修课 e[1] 指向后修课 e[0]，入度表示尚未完成的先修课数量。
g[e[1]].push_back(e[0]);
indeg[e[0]]++;
}
queue<int> q;
for (int i = 0; i < n; i++)
if (indeg[i] == 0)
q.push(i);
int finished = 0;
while (!q.empty()) {
int u = q.front();
q.pop();
finished++;
for (int v : g[u])
if (--indeg[v] == 0)
q.push(v);
}
return finished == n;
}
};
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, m;
cin >> n >> m;
vector<vector<int>> pre(m, vector<int>(2));
for (int i = 0; i < m; i++)
cin >> pre[i][0] >> pre[i][1];
cout << Solution().canFinish(n, pre) << '\n';
return 0;
}python
#!/usr/bin/env python3
from collections import deque
from typing import List
class Solution:
def canFinish(self, n: int, prerequisites: List[List[int]]) -> bool:
g = [[] for _ in range(n)]
indeg = [0] * n
for a, b in prerequisites:
g[b].append(a)
indeg[a] += 1
q = deque([i for i in range(n) if indeg[i] == 0])
cnt = 0
while q:
u = q.popleft()
cnt += 1
for v in g[u]:
indeg[v] -= 1
if indeg[v] == 0:
q.append(v)
return cnt == n
def main():
n, m = map(int, input().split())
pre = [list(map(int, input().split())) for _ in range(m)]
print(Solution().canFinish(n, pre))
if __name__ == "__main__":
main()复杂度
时间 O(V+E)，空间 O(V+E)。
总结
拓扑排序判环，图的边方向是"先修课 -> 课程"。