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