สมมติว่ามีหลักสูตรทั้งหมด 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]