LeetCode 207：课程表 | 拓扑排序
LeetCode 207：课程表 | 拓扑排序
引言
课程表（Course Schedule）是 LeetCode 第 207 题，难度为 Medium。题目要求判断是否可能完成所有课程的学习，即检测有向图是否有环。
算法实现
def canFinish(numCourses, prerequisites): graph = [[] for _ in range(numCourses)] indegree = [0] * numCourses for u, v in prerequisites: graph[v].append(u) indegree[u] += 1 queue = [i for i in range(numCourses) if indegree[i] == 0] visited = 0 while queue: node = queue.pop(0) visited += 1 for neighbor in graph[node]: indegree[neighbor] -= 1 if indegree[neighbor] == 0: queue.append(neighbor) return visited == numCourses复杂度分析
时间复杂度：O(V + E)
空间复杂度：O(V + E)
总结
拓扑排序可以检测有向图是否有环。