DFS正常课程表1的方法，注意判断有无环，有环返回空，无环返回后序遍历的结果
def findOrder(self, numCourses, prerequisites):
"""
:type numCourses: int
:type prerequisites: List[List[int]]
:rtype: List[int]
"""
self.flag = 0
g = [[]for _ in range(numCourses)]
for x,y in prerequisites: #注意邻接表的建立方式不同导致返回的后序遍历结果顺序不同，这里建立的依赖关系是x依赖于y,存储的是y指向的节点
g[y].append(x)
visited = [0]*numCourses
onpath = [0]*numCourses
self.res = []
def dfs(g,i):
if onpath[i] == 1:
self.flag = 1
if self.flag == 1 or visited[i] == 1:
return
onpath[i] = 1
visited[i] = 1
for course in g[i]:
dfs(g,course)
self.res.append(i)
onpath[i] = 0
for i in range(numCourses):
dfs(g,i)
if self.flag == 1:
return []
else:
return self.res[::-1]
BFS
def findOrder(self, numCourses, prerequisites):
"""
:type numCourses: int
:type prerequisites: List[List[int]]
:rtype: List[int]
"""
flag = 0
res = []
indegree = [0]*numCourses
g = [[]for _ in range(numCourses)]
for x,y in prerequisites:
g[y].append(x)
indegree[x] += 1
queue = deque()
for i in range(len(indegree)):
if indegree[i] == 0:
queue.append(i)
while queue:
for _ in range(len(queue)):
node = queue.popleft()
res.append(node)
flag += 1
for j in g[node]:
indegree[j] -= 1
if indegree[j] == 0:
queue.append(j)
if flag == numCourses:
return res
else:
return []
