假設總共有n個路線，這些路線從0到n-1標記。某些課程可能具有先決條件，鑒于課程總數(shù)和先決條件對列表，我們必須找到完成所有課程應采取的課程順序?？赡苡卸鄠€正確的訂單，我們只需要找到其中一個即可。如果不可能完成所有課程，則返回一個空數(shù)組。

因此，如果輸入為2 [[[1，0]]，則結(jié)果將為[0,1]。一共有2門課程。要選擇課程1，我們應該已經(jīng)完成課程0。因此正確的課程順序是[0,1]

為了解決這個問題，我們將遵循以下步驟-在main方法中，將需要numCourses和先決條件：這將類似于-

定義一個名為in_degree的數(shù)組，并填充所有節(jié)點的所有度數(shù)，以及圖的adj：=鄰接表

定義一個稱為訪問的數(shù)組，并用0填充，其大小與numCourses相同

定義一個空堆棧。

對于0到numCourses范圍內(nèi)的i返回一個空列表

如果將訪問堆棧傳遞到其中，則Visited [i]為假，而節(jié)點i的dfs為假，則

以相反的順序返回堆棧元素。

示例

讓我們看下面的實現(xiàn)以更好地理解-class?Solution(object):

def?findOrder(self,?numCourses,?prerequisites):

in_degree,adj=self.create_adj(numCourses,prerequisites)

visited?=?[0?for?i?in?range(numCourses)]

stack?=?[]

for?i?in?range(numCourses):

if?not?visited[i]?and?not?self.dfs(i,visited,stack,adj):

return?[]

return?stack[::-1]

def?create_adj(self,n,graph):

adj?=?{}

in_degree=?[0?for?i?in?range(n)]

for?i?in?graph:

in_degree[i[0]]+=1

if?i[1]?in?adj:

adj[i[1]].append(i[0])

else:

adj[i[1]]?=?[i[0]]

return?in_degree,adj

def?dfs(self,?node,?visited,stack,adj):

if?visited[node]?==?-1:

return?False

if?visited[node]?==?1:

return?True

visited[node]?=?-1

if?node?in?adj:

for?i?in?adj[node]:

if?not?self.dfs(i,visited,stack,adj):

return?False

visited[node]=1

stack.append(node)

return?True

ob?=?Solution()print(ob.findOrder(2,?[[1,0]]))

輸入項2

[[1,0]]

輸出結(jié)果[0,1]

總結(jié)

以上是生活随笔為你收集整理的python自己做课程表_Python课程表II的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。