題目鏈接
難度：中等 ??????類型： 圖
現(xiàn)在你總共有 n 門課需要選，記為 0 到 n-1缸棵。
在選修某些課程之前需要一些先修課程舟茶。 例如，想要學(xué)習(xí)課程 0 堵第，你需要先完成課程 1 吧凉，我們用一個匹配來表示他們: [0,1]
給定課程總量以及它們的先決條件，返回你為了學(xué)完所有課程所安排的學(xué)習(xí)順序踏志。
可能會有多個正確的順序阀捅，你只要返回一種就可以了。如果不可能完成所有課程针余，返回一個空數(shù)組饲鄙。
示例1
輸入: 2, [[1,0]]
輸出: [0,1]
解釋: 總共有 2 門課程。要學(xué)習(xí)課程 1圆雁，你需要先完成課程 0忍级。因此，正確的課程順序為 [0,1] 伪朽。
示例2
輸入: 4, [[1,0],[2,0],[3,1],[3,2]]
輸出: [0,1,2,3] or [0,2,1,3]
解釋: 總共有 4 門課程轴咱。要學(xué)習(xí)課程 3，你應(yīng)該先完成課程 1 和課程 2驱负。并且課程 1 和課程 2 都應(yīng)該排在課程 0 之后嗦玖。
因此，一個正確的課程順序是 [0,1,2,3] 跃脊。另一個正確的排序是 [0,2,1,3] 宇挫。
解題思路
遍歷輸入中的所有邊，創(chuàng)建鄰接表,out_degree[i]存儲所有把第i節(jié)課作為預(yù)備課程的課酪术，并用in_degree[i]存儲結(jié)點i的入度器瘪。
將所有入度為0的邊加入 res
執(zhí)行以下操作直到 res中不再增加元素：
遍歷res中的元素翠储。不妨稱為 N。對 N的所有鄰接節(jié)點, 將其入度減去1橡疼。若任意結(jié)點的入度變?yōu)?援所，將其加入res。
代碼實現(xiàn)
class Solution(object):
def findOrder(self, numCourses, prerequisites):
"""
:type numCourses: int
:type prerequisites: List[List[int]]
:rtype: List[int]
"""
in_degree = [0] * numCourses
out_degree = [[] for _ in range(numCourses)]
for course, pre in prerequisites:
in_degree[course] += 1
out_degree[pre].append(course)
res = []
for i in range(numCourses):
if in_degree[i] == 0:
res.append(i)
l = 0
while l != len(res):
x = res[l]
l += 1
for i in out_degree[x]:
in_degree[i] -= 1
if in_degree[i] == 0:
res.append(i)
return res if l == numCourses else []
