Computer >> คอมพิวเตอร์ >  >> การเขียนโปรแกรม >> Python

ตารางหลักสูตร II ใน Python


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