Lịch trình khóa học bằng Python

Giả sử có tổng số khóa học numCourses mà chúng ta phải tham gia, được gắn nhãn từ 0 đến numCourses-1. Một số khóa học có thể có các điều kiện tiên quyết, ví dụ để học khóa 0, trước tiên chúng ta phải học khóa 1, được biểu thị bằng cặp:[0,1]. Giả sử có tổng số khóa học được cung cấp và danh sách các cặp điều kiện tiên quyết, chúng tôi phải kiểm tra xem bạn có thể hoàn thành tất cả các khóa học không?

Vì vậy, nếu đầu vào là - numCourses =2 và điều kiện tiên quyết =[[1, 0]], thì kết quả sẽ là true, vì có tổng cộng 2 khóa học cần thực hiện. Để tham gia khóa học 1, chúng ta nên hoàn thành khóa học 0. Vì vậy, có thể.

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• Trong phương thức chính, nó sẽ sử dụng numCourses và điều kiện tiên quyết:Điều này sẽ hoạt động giống như -

• nếu điều kiện tiên quyết không có mục nhập, thì trả về true

• tạo một mảng được gọi là đã thăm, điền vào mảng này bằng 0 và phạm vi của nó giống như numCourses

• adj_list:=tạo một biểu đồ bằng cách sử dụng các điều kiện tiên quyết

• cho tôi trong phạm vi từ 0 đến numCourses

  • nếu lượt truy cập [i] là sai, thì

    • nếu không có chu kỳ nào giữa các nút đã truy cập trong biểu đồ, hãy trả về false

• trả về true

Ví dụ

Hãy cùng chúng tôi xem cách triển khai sau đây để hiểu rõ hơn -

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]]))

Đầu vào

2
[[1,0]]

Đầu ra

true