পাইথনে দِيয়ে गये এজগুলো অন্তর্ভুক্ত করে অনন্য পথের সংখ্যা গণনার প্রোগ্রাম

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

উদাহরণস্বরূপ, ইনপুট edges = [[0, 1],[0, 2],[1, 3],[1, 4]] হলে আউটপুট হবে [6, 4, 4, 4]।

সমাধানের ধাপসমূহ

• adj := দেওয়া এজlardan অ্যাডজেসেন্সি লিস্ট তৈরি করুন
• count := একটি খালি মানচিত্র
• dfs(x, parent) ফাংশন সংজ্ঞায়িত করুন:
  • count[x] := 1
  • adj[x] এর প্রতিটি প্রতিবেশী nb এর জন্য:
    • যদি nb == parent, তবে চালিয়ে যান
    • count[x] := count[x] + dfs(nb, x)
  • count[x] ফেরত দিন
• মূল পদ্ধতিতে:
  • dfs(0, -1) কল করুন
  • ans := []
  • প্রতিটি এজ (a, b) এর জন্য:
    • x := min(count[a], count[b])
    • ans তে 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]