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

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

इसलिए, यदि इनपुट किनारों की तरह है =[[0, 1],[0, 2],[1, 3],[1, 4]]

तो आउटपुट [6, 4, 4, 4] होगा।

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -

• adj :=दिए गए किनारों से आसन्नता सूची

• गिनती :=एक खाली नक्शा

• फ़ंक्शन को परिभाषित करें dfs() । इसमें x, पैरेंट

  लगेगा

• गिनती [x] :=1

• adj[x] में प्रत्येक nb के लिए, करें

  • यदि nb माता-पिता के समान है, तो

    • लूप से बाहर आएं

  • गिनती [एक्स]:=गिनती [एक्स] + डीएफएस (एनबी, एक्स)

• वापसी की संख्या[x]

• मुख्य विधि से निम्न कार्य करें -

• dfs(0, -1)

• उत्तर :=एक नई सूची

• किनारों में प्रत्येक किनारे (ए, बी) के लिए, करें

  • x :=न्यूनतम गिनती[a] और गिनती[b]

  • उत्तर के अंत में (x *(गिनती[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]