Giả sử có tổng cộng n khóa học, chúng được gắn nhãn từ 0 đến n-1. Một số khóa học có thể có điều kiện tiên quyết, với tổng số khóa học và danh sách các cặp điều kiện tiên quyết, chúng ta phải tìm thứ tự các khóa học mà chúng ta nên thực hiện để hoàn thành tất cả các khóa học. Có thể có nhiều đơn đặt hàng đúng, chúng tôi chỉ cần tìm một trong số chúng. Nếu không thể hoàn thành tất cả các khóa học, hãy trả về một mảng trống.
Vì vậy, nếu đầu vào là 2, [[1, 0]], thì kết quả sẽ là [0,1]. Có tổng cộng 2 khóa học để tham gia. Để tham gia khóa học số 1, chúng ta phải hoàn thành khóa học 0. Vì vậy, thứ tự khóa học chính xác là [0,1]
Để 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ư -
-
Xác định một mảng được gọi là in_degree và điền tất cả theo độ của tất cả các nút và adj:=danh sách kề của biểu đồ
-
Xác định một mảng được gọi là đã thăm và điền vào mảng này bằng 0, kích thước của nó giống như numCourses
-
Xác định một ngăn xếp trống.
-
cho tôi trong phạm vi từ 0 đến numCourses
-
nếu đã thăm [i] là sai và dfs của nút i là sai bằng cách chuyển ngăn xếp vào đó, thì
-
trả về một danh sách trống
-
-
-
trả về các phần tử ngăn xếp theo thứ tự ngược lại.
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 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]])) Đầu vào
2 [[1,0]]
Đầu ra
[0,1]