ตารางเรียนในภาษา Python

สมมติว่ามีหลักสูตร numCourses ทั้งหมดที่เราต้องทำ โดยมีป้ายกำกับตั้งแต่ 0 ถึง numCourses-1 บางหลักสูตรอาจมีข้อกำหนดเบื้องต้น เช่น หากต้องการเรียนหลักสูตร 0 เราต้องเรียนหลักสูตร 1 ก่อน ซึ่งแสดงโดยใช้คู่:[0,1] สมมุติว่ามีจำนวนรายวิชาที่จัดให้ทั้งหมดและมีรายชื่อคู่บังคับก่อน เราต้องตรวจสอบก่อนว่าท่านจะเรียนจบครบทุกหลักสูตรหรือไม่

ดังนั้นหากข้อมูลเข้าเป็น − numCourses =2 และข้อกำหนดเบื้องต้น =[[1, 0]] ผลลัพธ์จะเป็นจริง เพราะมีทั้งหมด 2 วิชาที่ต้องทำ การเข้าคอร์สที่ 1 เราควรจบคอร์ส 0 ได้แล้ว ดังนั้นมันจึงเป็นไปได้

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• ในวิธีการหลัก จะใช้ numCourses และข้อกำหนดเบื้องต้น:สิ่งนี้จะทำหน้าที่เหมือน −

• หากข้อกำหนดเบื้องต้นไม่มีรายการให้คืนค่า true

• สร้างอาร์เรย์ที่เรียกว่า visited เติมค่านี้ด้วย 0 และช่วงของอาร์เรย์จะเหมือนกับ numCourses

• adj_list :=สร้างกราฟโดยใช้ข้อกำหนดเบื้องต้น

• สำหรับฉันอยู่ในช่วง 0 ถึง numCourses

  • ถ้ามาเยี่ยม[i] จะเป็นเท็จ แล้ว

    • หากไม่มีรอบระหว่างโหนดที่เข้าชมในกราฟ ให้คืนค่าเท็จ

• คืนความจริง

ตัวอย่าง

ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -

class Solution(object):
   def canFinish(self, numCourses, prerequisites):
      if len(prerequisites) == 0:
         return True
      visited = [0 for i in range(numCourses)]
      adj_list = self.make_graph(prerequisites)
      for i in range(numCourses):
         if not visited[i]:
            if not self.cycle(adj_list,visited,i):
               return False
      return True
   def cycle(self,adj_list,visited,current_node = 0):
      if visited[current_node] ==-1:
         return False
      if visited[current_node] == 1:
         return True
      visited[current_node] = -1
      if(current_node in adj_list):
         for i in adj_list[current_node]:
            if not self.cycle(adj_list,visited,i):
               return False
      visited[current_node] = 1
      return True
   def make_graph(self,array):
      adj_list = {}
      for i in array:
         if i[1] in adj_list:
            adj_list[i[1]].append(i[0])
         else:
            adj_list[i[1]] = [i[0]]
      return adj_list
ob = Solution()
print(ob.canFinish(2, [[1,0]]))

อินพุต

2
[[1,0]]

ผลลัพธ์

true