資料結構
網路
關係型資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法學Python課程安排II
假設共有n門課程，編號從0到n-1。一些課程可能有先修課程，給定課程總數和先修課程對列表，我們必須找到完成所有課程的課程順序。可能有多個正確的順序，我們只需要找到其中一個。如果無法完成所有課程，則返回空陣列。
因此，如果輸入類似於2，[[1, 0]]，則結果將是[0,1]。共有2門課程需要學習。要學習課程編號1，我們應該已經完成了課程0。所以正確的課程順序是[0,1]
為了解決這個問題，我們將遵循以下步驟：
在主方法中，它將採用numCourses和prerequisites：這將起到以下作用：
定義一個名為in_degree的陣列，並填充所有節點的所有入度，adj := 圖的鄰接表
定義一個名為visited的陣列，並用0填充它，其大小與numCourses相同
定義一個空棧。
對於範圍0到numCourses中的i
如果visited[i]為false，並且透過將堆疊傳遞給它，節點i的dfs為false，則
返回空列表
以反序返回堆疊元素。
示例
讓我們看看下面的實現，以便更好地理解：
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]]
輸出
[0,1]
更新於：2020年4月29日
276 次瀏覽
廣告