Giả sử chúng ta có một đồ thị xoay chiều có hướng, với n đỉnh và các nút được đánh số từ 0 đến n-1, đồ thị được biểu diễn bởi một danh sách cạnh, trong đó các cạnh [i] =(u, v) biểu thị một cạnh có hướng từ nút u đến nút v. Chúng ta phải tìm tập đỉnh nhỏ nhất mà từ đó tất cả các nút trong đồ thị đều có thể truy cập được. (Chúng tôi có thể trả về các đỉnh theo bất kỳ thứ tự nào).
Vì vậy, nếu đầu vào giống như
thì đầu ra sẽ là [0,2,3] vì hai đỉnh này không thể đạt tới từ bất kỳ đỉnh nào khác, vì vậy nếu chúng ta bắt đầu từ chúng, chúng ta có thể bao quát tất cả.
Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -
-
n:=kích thước của các cạnh
-
all_nodes:=một tập hợp mới từ phạm vi 0 đến n
-
v:=một tập hợp mới
-
đối với mỗi cạnh (i, j) trong các cạnh, thực hiện
-
thêm j vào v
-
-
ans:=xóa tất cả các cạnh chung khỏi all_nodes và v khỏi all_nodes
-
trả lại ans
Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -
Ví dụ
def solve(edges): n = len(edges) all_nodes = set(range(n)) v = set() for edge in edges: v.add(edge[1]) ans = all_nodes - v return ans edges = [(0,1),(2,1),(3,1),(1,4),(2,4)] print(solve(edges))
Đầu vào
[(0,1),(2,1),(3,1),(1,4),(2,4)]
Đầu ra
{0, 2, 3}