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)总结拓扑排序可以检测有向图是否有环。