โปรแกรมนับจำนวนเส้นทางที่ไม่ซ้ำซึ่งรวมถึงขอบที่กำหนดใน Python

สมมติว่าเรามีรายการของขอบในรูปแบบ (u, v) และสิ่งเหล่านี้เป็นตัวแทนของต้นไม้ สำหรับแต่ละขอบ เราต้องหาจำนวนเส้นทางที่ไม่ซ้ำทั้งหมดที่มีขอบดังกล่าว ในลำดับเดียวกันกับที่ระบุในอินพุต

ดังนั้น ถ้าอินพุตเหมือน edge =[[0, 1],[0, 2],[1, 3],[1, 4]]

จากนั้นผลลัพธ์จะเป็น [6, 4, 4, 4]

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

• adj :=รายการที่อยู่ติดกันจากขอบที่กำหนด

• นับ :=แผนที่ว่างเปล่า

• กำหนดฟังก์ชัน dfs() นี่จะใช้เวลา x พาเรนต์

• นับ[x] :=1

• สำหรับแต่ละ nb ใน adj[x] ทำ

  • ถ้า nb เหมือนกับ parent แล้ว

    • ออกจากวง

  • นับ[x] :=นับ[x] + dfs(nb, x)

• จำนวนคืน[x]

• จากวิธีหลัก ให้ทำดังต่อไปนี้ −

• dfs(0, -1)

• ans :=รายการใหม่

• สำหรับแต่ละขอบ (a, b) ในขอบ ทำ

  • x :=จำนวนขั้นต่ำ[a] และจำนวน[b]

  • แทรก (x *(count[0] - x)) ต่อท้ายคำตอบ

• กลับมาอีกครั้ง

ตัวอย่าง

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

from collections import defaultdict
class Solution:
   def solve(self, edges):
      adj = defaultdict(list)
      for a, b in edges:
         adj[a].append(b)
         adj[b].append(a)
      count = defaultdict(int)
      def dfs(x, parent):
         count[x] = 1
         for nb in adj[x]:
            if nb == parent:
               continue
            count[x] += dfs(nb, x)
         return count[x]
      dfs(0, -1)
      ans = []
      for a, b in edges:
         x = min(count[a], count[b])
         ans.append(x * (count[0] - x))
      return ans
ob = Solution()
edges = [
   [0, 1],
   [0, 2],
   [1, 3],
   [1, 4]
]
print(ob.solve(edges))

อินพุต

[
   [0, 1],
   [0, 2],
   [1, 3],
   [1, 4]
]

ผลลัพธ์

[6, 4, 4, 4]