【hot100篇-python刷题记录】【课程表】

R7-图论篇

思路：DFS搜索，只要形成的图不存在闭环即可完成。

class Solution:def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:def dfs(i,adj,flags):if flags[i]==-1:return Trueif flags[i]==1:return Falseflags[i]=1for j in adj[i]:if not dfs(j,adj,flags):return Falseflags[i]=-1return True#创建邻接矩阵分别表示每个先修课程的后修课程adj=[[]for _ in range(numCourses)]flags=[0 for _ in range(numCourses)]for cur,pre in prerequisites:adj[pre].append(cur)for i in range(numCourses):if not dfs(i,adj,flags):return Falsereturn True