สมมติว่ามีหลักสูตรทั้งหมด n หลักสูตร โดยจะมีป้ายกำกับตั้งแต่ 0 ถึง n-1 บางหลักสูตรอาจมีข้อกำหนดเบื้องต้น เมื่อพิจารณาจากจำนวนหลักสูตรทั้งหมดและรายชื่อคู่ข้อกำหนดเบื้องต้น เราต้องหาลำดับหลักสูตรที่ควรทำเพื่อจบหลักสูตรทั้งหมด อาจมีคำสั่งซื้อที่ถูกต้องหลายรายการ เราแค่ต้องหาคำสั่งซื้อหนึ่งรายการ หากไม่สามารถจบทุกหลักสูตรได้ ให้คืนค่าอาร์เรย์ว่าง
ดังนั้นหากอินพุตเป็น 2, [[1, 0]] ผลลัพธ์จะเป็น [0,1] มีทั้งหมด 2 คอร์สให้เลือก ในการเรียนหลักสูตรที่ 1 เราควรจบหลักสูตร 0 ดังนั้นลำดับหลักสูตรที่ถูกต้องคือ [0,1]
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
-
ในวิธีการหลัก จะใช้ numCourses และข้อกำหนดเบื้องต้น:สิ่งนี้จะทำหน้าที่เหมือน −
-
กำหนดอาร์เรย์ที่เรียกว่า in_degree และเติมด้วยองศาของโหนดทั้งหมดทั้งหมด และ adj :=รายการที่อยู่ติดกันของกราฟ
-
กำหนดหนึ่งอาร์เรย์ที่เรียกว่าเยี่ยมชมแล้วเติมค่านี้ด้วย 0 ขนาดของอาร์เรย์จะเท่ากับ numCourses
-
กำหนดหนึ่งสแต็กว่าง
-
สำหรับฉันอยู่ในช่วง 0 ถึง numCourses
-
หากการเยี่ยมชม[i] เป็นเท็จและ dfs ของโหนด i เป็นเท็จโดยส่งสแต็กเข้าไป
-
กลับรายการว่าง
-
-
-
ส่งคืนองค์ประกอบสแต็กในลำดับย้อนกลับ
ตัวอย่าง
ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -
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]
