Giả sử ta có một loại đồ thị đặc biệt có hai loại đỉnh: head (đầu) và feet (chân). Đồ thị chỉ có một head và có k cạnh nối head đến từng feet. Cho một đồ thị vô hướng, không trọng số, ta phải tìm các đồ thị con đặc biệt này trong các đồ thị con rời nhau theo đỉnh. Hai đồ thị gọi là rời nhau theo đỉnh nếu không có đỉnh chung.
Ví dụ, với đầu vào như hình minh họa, số đỉnh n = 5, số feet t = 2, đầu ra sẽ là 5.
Có thể có 5 đồ thị đặc biệt rời nhau theo đỉnh của đồ thị cho trước.
Giải pháp
Để giải quyết bài toán này, ta thực hiện các bước sau:
- G := danh sách mới chứa n+1 danh sách rỗng
- Với mỗi item trong edges:
- s := item[0], d := item[1]
- Thêm d vào G[s], thêm s vào G[d]
- visit := map mới
- Với i từ 0 đến n:
- v := G[i]
- Nếu kích thước v == 1:
- s := v[0]
- Nếu s không trong visit: visit[s] := [i]
- Ngược lại: thêm i vào visit[s]
- Ngược lại nếu kích thước v == 0: n := n - 1
- tmp := 0
- Với mỗi k trong visit:
- x := kích thước visit[k] - t
- Nếu x > 0: tmp := tmp + x
- Trả về n - tmp
Ví dụ minh họa
Xem triển khai sau để hiểu rõ hơn:
def solve(n, t, edges):
G = [[] for _ in range(n + 1)]
for item in edges:
s, d = map(int, item)
G[s].append(d)
G[d].append(s)
visit = {}
for i in range(n):
v = G[i]
if len(v) == 1:
s = v[0]
if s not in visit:
visit[s] = [i]
else:
visit[s].append(i)
elif len(v) == 0:
n -= 1
tmp = 0
for k in visit:
x = len(visit[k]) - t
if x > 0:
tmp += x
return n - tmp
print(solve(6, 2, [(1,4), (2,4), (3,4), (3,4), (5,3), (6,3)]))
Đầu vào
6, 2, [(1,4), (2,4), (3,4), (3,4), (5,3), (6,3)]
Đầu ra
5