Cho DAG n đỉnh (0..n-1), danh sách cạnh edges[i]=(u,v) có hướng u→v. Tìm tập đỉnh nhỏ nhất sao cho từ chúng có thể đạt được mọi node. Trả về tập đỉnh (thứ tự bất kỳ).
Ví dụ: edges=[(0,1),(2,1),(3,1),(1,4),(2,4)] → {0,2,3} (các đỉnh không có cạnh vào).
Thuật toán
- n = len(edges)
- all_nodes = set(range(n))
- v = set() chứa các đỉnh có cạnh vào (destination)
- Duyệt edges: thêm edge[1] vào v
- ans = all_nodes - v (đỉnh không có cạnh vào)
- Return ans
Code Python
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))
Input
[(0,1),(2,1),(3,1),(1,4),(2,4)]
Output
{0, 2, 3}