ค้นหาจำนวนจุดยอดคู่ที่แตกต่างกันซึ่งมีระยะทางเท่ากับ k ในต้นไม้ใน Python

สมมติว่าเรามีจำนวนเต็ม k และมีต้นไม้ที่มี n โหนดด้วย เราต้องนับจำนวนจุดยอดคู่ที่แตกต่างกันซึ่งมีระยะทาง k ที่แน่นอน

ดังนั้นหากอินพุตเป็น k =2

แล้วผลลัพธ์จะเป็น 4

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• ไม่มี :=5005

• กราฟ :=รายการที่อยู่ติดกันของขนาด N

• vertex_count :=เมทริกซ์ 2 มิติขนาด 505 x 5005

• res :=0

• กำหนดฟังก์ชัน insert_edge() นี่จะใช้เวลา x, y

  • แทรก y ที่ส่วนท้ายของกราฟ[x]

  • แทรก x ที่ส่วนท้ายของกราฟ[y]

• กำหนดฟังก์ชัน dfs() นี่จะใช้เวลา v, parent

• vertex_count[v, 0] :=1

• สำหรับแต่ละ i ในกราฟ[v] ทำ

  • ถ้าฉันไม่เหมือนผู้ปกครองแล้ว

    • dfs(i, v)

    • สำหรับ j ในช่วง 1 ถึง k + 1 ทำ

      • res :=res + vertex_count[i, j - 1] * vertex_count[v, k - j]

    • สำหรับ j ในช่วง 1 ถึง k + 1 ทำ

      • vertex_count[v, j] :=vertex_count[v, j] + vertex_count[i, j - 1]

ตัวอย่าง

ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -

N = 5005
graph = [[] for i in range(N)]
vertex_count = [[0 for i in range(505)] for i in range(N)]
res = 0
def insert_edge(x, y):
   graph[x].append(y)
   graph[y].append(x)
def dfs(v, parent):
   global res
   vertex_count[v][0] = 1
   for i in graph[v]:
      if (i != parent):
         dfs(i, v)
         for j in range(1, k + 1):
            res += vertex_count[i][j - 1] * vertex_count[v][k - j]
         for j in range(1, k + 1):
            vertex_count[v][j] += vertex_count[i][j - 1]
k = 2
insert_edge(1, 2)
insert_edge(2, 3)
insert_edge(3, 4)
insert_edge(2, 5)
dfs(1, 0)
print(res)

อินพุต

k = 2
insert_edge(1, 2)
insert_edge(2, 3)
insert_edge(3, 4)
insert_edge(2, 5)

ผลลัพธ์

4