পাইথনে প্রদত্ত প্রান্তগুলি অন্তর্ভুক্ত করে এমন অনন্য পাথের সংখ্যা গণনা করার প্রোগ্রাম

ধরুন আমাদের (u, v) আকারে প্রান্তগুলির একটি তালিকা রয়েছে এবং এগুলি একটি গাছের প্রতিনিধিত্ব করছে। প্রতিটি প্রান্তের জন্য আমাদেরকে ইনপুটে দেওয়া একই ক্রমে অনন্য পাথের মোট সংখ্যা খুঁজে বের করতে হবে যাতে উল্লিখিত প্রান্তটি অন্তর্ভুক্ত থাকে।

সুতরাং, যদি ইনপুটটি প্রান্তের মত হয় =[[0, 1],[0, 2],[1, 3],[1, 4]]

তাহলে আউটপুট হবে [6, 4, 4, 4]।

এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -

• adj :=প্রদত্ত প্রান্ত থেকে সংলগ্ন তালিকা

• গণনা :=একটি খালি মানচিত্র

• একটি ফাংশন dfs() সংজ্ঞায়িত করুন। এটি x, অভিভাবক

  লাগবে

• গণনা [x] :=1

• adj[x]-এ প্রতিটি nb-এর জন্য, do

  • যদি nb অভিভাবক হিসাবে একই হয়, তাহলে

    • লুপ থেকে বেরিয়ে আসুন

  • গণনা [x] :=গণনা [x] + dfs(nb, x)

• ফেরত সংখ্যা[x]

• প্রধান পদ্ধতি থেকে নিম্নলিখিতগুলি করুন -

• dfs(0, -1)

• উত্তর :=একটি নতুন তালিকা

• প্রতিটি প্রান্তের জন্য (a, b) প্রান্তে, করুন

  • 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]