สมมติว่าเรามีกราฟประเภทพิเศษที่มีสองประเภทของจุดยอดคือ head และ feet กราฟมี head เพียงตัวเดียว และมี k เส้นขอบเชื่อม head ไปยังแต่ละ feet ถ้าเราได้รับกราฟไม่มีทิศทาง ไม่มีน้ำหนัก เราต้องหาย่อยกราฟประเภทพิเศษเหล่านี้ในซับกราฟที่เป็น vertex disjoint ของกราฟ สองกราฟถือว่า vertex disjoint ถ้าไม่มีจุดยอดร่วมกัน
เช่น ถ้าอินพุตเป็นดังภาพ จำนวนโหนด (n) = 5 จำนวน feet (t) = 2 ผลลัพธ์จะเป็น 5 สามารถมีซับกราฟประเภทพิเศษ 5 ตัวที่เป็น vertex disjoint ของกราฟที่กำหนด
วิธีแก้ปัญหา
- G := รายการใหม่ที่มี n+1 รายการว่าง
- สำหรับแต่ละ item ใน edges:
- s := item[0], d := item[1]
- แทรก d ลงท้าย G[s], แทรก s ลงท้าย G[d]
- visit := แมปใหม่
- สำหรับ i ในช่วง 0 ถึง n:
- v := G[i]
- ถ้าขนาดของ v เท่ากับ 1:
- s := v[0]
- ถ้า s ไม่อยู่ใน visit: visit[s] := [i]
- มิฉะนั้น: เพิ่ม i ลงท้าย visit[s]
- มิฉะนั้นถ้าขนาดของ v เท่ากับ 0: n := n - 1
- tmp := 0
- สำหรับแต่ละ k ใน visit:
- x := ขนาดของ visit[k] - t
- ถ้า x > 0: tmp := tmp + x
- return n - tmp
ตัวอย่าง
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)]))
อินพุต
6, 2, [(1,4), (2,4), (3,4), (3,4), (5,3), (6,3)]
เอาต์พุต
5
