相关题目：
207. 课程表
210. 课程表 II
630. 课程表 III
1462. 课程表 IV
class CourseSchedule:
"""
207.课程表
https://leetcode.cn/problems/course-schedule/
"""
def __init__(self):
# 记录⼀次递归堆栈中的节点
self.onPath = []
# 记录遍历过的节点，防⽌⾛回头路
self.visited = []
# 记录图中是否有环
self.hasCycle = False
def buildGraph(self, numCourses: int, prerequisites: List[List[int]]) -> List[List[int]]:
# 注意这两种新建对象的区别，前者是传的引用，后者是拷贝一个新的变量
# graph = [[]] * numCourses
graph = [[] for _ in range(numCourses)]
for edge in prerequisites:
src = edge[1]
dst = edge[0]
graph[src].append(dst)
return graph
def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
"""
dfs
:param numCourses:
:param prerequisites:
:return:
"""
graph = self.buildGraph(numCourses, prerequisites)
self.visited = [False] * numCourses
self.onPath = [False] * numCourses
for i in range(numCourses):
self.traverse(graph, i)
return not self.hasCycle
def traverse(self, graph, i):
if self.onPath[i]:
self.hasCycle = True
return
if self.visited[i]:
return
self.visited[i] = True
self.onPath[i] = True
for t in graph[i]:
self.traverse(graph, t)
self.onPath[i] = False
def canFinish2(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
"""
bfs
:param numCourses:
:param prerequisites:
:return:
"""
graph = [[] for _ in range(numCourses)]
indegree = [0] * numCourses
for edge in prerequisites:
src = edge[1]
dst = edge[0]
graph[src].append(dst)
indegree[dst] += 1
queue = []
for i in range(numCourses):
if indegree[i] == 0:
queue.append(i)
visited = 0
while queue:
cur = queue.pop(0)
visited += 1
for v in graph[cur]:
indegree[v] -= 1
if indegree[v] == 0:
queue.append(v)
# 最后只需要判断已访问的课程数是否等于课程总数即可
return visited == numCourses
# 210. 课程表 II
class Solution:
def __init__(self):
self.hascycle = False
self.postorder = []
def buildGraph(self, numCourses: int, prerequisites: List[List[int]]) -> List[List[int]]:
# 注意这两种新建对象的区别，前者是传的引用，后者是拷贝一个新的变量
# graph = [[]] * numCourses
graph = [[] for _ in range(numCourses)]
for edge in prerequisites:
src = edge[1]
dst = edge[0]
graph[src].append(dst)
return graph
def findOrder(self, numCourses: int, prerequisites: List[List[int]]) -> List[int]:
graph = self.buildGraph(numCourses, prerequisites)
self.indegree = [0] * numCourses
# 计算入度，和环检测算法相同
for edge in prerequisites:
dst = edge[0]
self.indegree[dst] += 1
# 根据入度初始化队列中的节点，和环检测算法相同
queue = []
for i in range(numCourses):
if self.indegree[i] == 0:
queue.append(i)
res = [0] * numCourses
# 记录遍历节点的顺序
count = 0
while queue:
cur = queue.pop(0)
# 弹出节点的顺序即为拓扑排序结果
res[count] = cur
count += 1
for neighbor in graph[cur]:
self.indegree[neighbor] -= 1
if self.indegree[neighbor] == 0:
queue.append(neighbor)
# 存在环
if count != numCourses:
return []
return res
# 630. 课程表 III
# 这道题本质上用得是贪心算法或动态规划，和其他几道课程表题的解题思路不太一样。
import heapq
class Solution:
def scheduleCourse(self, courses: List[List[int]]) -> int:
courses.sort(key=lambda c: c[1])
q = list()
# 优先队列中所有课程的总时间
total = 0
# 从大根堆中依次取出 t值最大的那门课程
for ti, di in courses:
# 如果当前队列中所有课程的总时间与ti之和小于等于di，就把ti加入优先级队列
if total + ti <= di:
total += ti
# Python 默认是小根堆
heapq.heappush(q, -ti)
# 如果 当前队列中所有课程的总时间与ti之和大于di，就找出堆顶的元素，和当前元素t1进行比较，
# 如果大于ti，就替换掉堆顶元素
elif q and -q[0] > ti:
total -= -q[0] - ti
heapq.heappop(q)
heapq.heappush(q, -ti)
return len(q)
# 1462. 课程表 IV
class Solution:
def checkIfPrerequisite(self, numCourses: int, prerequisites: List[List[int]], queries: List[List[int]]) -> List[bool]:
g = [[] for _ in range(numCourses)]
indgree = [0] * numCourses
isPre = [[False] * numCourses for _ in range(numCourses)]
for p in prerequisites:
indgree[p[1]] += 1
g[p[0]].append(p[1])
q = []
# 将入度为0的节点加入队列
for i in range(numCourses):
if indgree[i] == 0:
q.append(i)
while q:
cur = q.pop(0)
for ne in g[cur]:
isPre[cur][ne] = True
for i in range(numCourses):
isPre[i][ne] = isPre[i][ne] or isPre[i][cur]
indgree[ne] -= 1
if indgree[ne] == 0:
q.append(ne)
res = []
for query in queries:
res.append(isPre[query[0]][query[1]])
return res