पायथन में दिए गए एज को शामिल करने वाले अद्वितीय पथों की संख्या गिनने का प्रोग्राम

मान लीजिए हमारे पास (u, v) के रूप में एज की सूची है जो एक ट्री दर्शाती है। प्रत्येक एज के लिए हमें उन अद्वितीय पथों की कुल संख्या ज्ञात करनी है जिनमें वह एज शामिल है, उसी क्रम में जैसे इनपुट में दिया गया है।

उदाहरण के लिए, यदि इनपुट है edges = [[0, 1],[0, 2],[1, 3],[1, 4]], तो आउटपुट [6, 4, 4, 4] होगा।

एल्गोरिदम

• adj := दिए गए एज से एडजेसेंसी लिस्ट
• count := खाली मैप
• dfs(x, parent) फ़ंक्शन परिभाषित करें:
  • count[x] := 1
  • प्रत्येक पड़ोसी nb के लिए adj[x] में:
    • यदि nb == parent, तो जारी रखें
    • count[x] += dfs(nb, x)
  • count[x] वापस करें
• मुख्य विधि से:
  • dfs(0, -1) कॉल करें
  • ans := नई सूची
  • प्रत्येक एज (a, b) के लिए:
    • x := min(count[a], count[b])
    • ans.append(x * (count[0] - x))
  • ans वापस करें

उदाहरण

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]