Giả sử có một đồ thị sao vô hướng n đỉnh đánh số 1 đến n. Đồ thị sao có 1 tâm và n-1 cạnh nối tâm với mọi đỉnh khác. Tìm tâm của đồ thị sao cho trước.
Ví dụ: đầu vào như hình, đầu ra = 3 (vì 3 là tâm).
Giải pháp
Tâm của đồ thị sao là đỉnh xuất hiện trong mọi cạnh. Chỉ cần duyệt các cạnh, đỉnh xuất hiện 2 lần là tâm:
- seen := tập hợp mới
- Với mỗi cạnh (u,v) trong graph:
- Nếu u trong seen: trả về u
- Nếu v trong seen: trả về v
- Thêm u, v vào seen
Ví dụ minh họa
Xem triển khai sau để hiểu rõ hơn:
def solve(graph):
seen = set()
for u, v in graph:
if u in seen:
return u
if v in seen:
return v
seen.add(u)
seen.add(v)
graph = [(1,3),(2,3),(4,3),(5,3),(6,3)]
print(solve(graph))
Đầu vào
[(1,3),(2,3),(4,3),(5,3),(6,3)]
Đầu ra
3