পাইথনে সমস্ত শহরের সর্বাধিক সম্ভাব্য জনসংখ্যা খুঁজে পাওয়ার প্রোগ্রাম

N নোড এবং N-1 প্রান্ত সহ একটি বৃক্ষ হিসাবে উপস্থাপিত একটি দেশ বিবেচনা করুন। এখন প্রতিটি নোড একটি শহরের প্রতিনিধিত্ব করে, এবং প্রতিটি প্রান্ত একটি রাস্তা প্রতিনিধিত্ব করে। আমাদের কাছে N-1 আকারের সংখ্যার উৎস এবং গন্তব্যের দুটি তালিকা রয়েছে। তাদের মতে i-th রাস্তা উৎস [i] থেকে গন্তব্য [i] সংযোগ করে। আর রাস্তাগুলো দ্বিমুখী। আমাদের কাছে সংখ্যার আরেকটি তালিকা রয়েছে যাকে N আকারের জনসংখ্যা বলা হয়, যেখানে জনসংখ্যা [i] i-th শহরের জনসংখ্যাকে প্রতিনিধিত্ব করে। আমরা কিছু সংখ্যক শহরকে শহরে উন্নীত করার চেষ্টা করছি। কিন্তু কোন দুটি শহর একে অপরের সংলগ্ন হওয়া উচিত নয় এবং একটি শহরের সংলগ্ন প্রতিটি নোড একটি শহর হওয়া উচিত (প্রতিটি রাস্তা একটি শহর এবং একটি শহরকে সংযুক্ত করতে হবে)। তাই আমাদের সব শহরের সম্ভাব্য সর্বাধিক জনসংখ্যা খুঁজে বের করতে হবে।

সুতরাং, যদি ইনপুটটি উৎস =[2, 2, 1, 1] dest =[1, 3, 4, 0] জনসংখ্যা =[6, 8, 4, 3, 5] এর মতো হয়, তাহলে আউটপুট হবে 15, 6 + 4 + 5 =15 জনসংখ্যা পেতে আমরা 0, 2, এবং 4 শহরগুলিকে আপগ্রেড করতে পারি৷

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

adj :=উৎস এবং গন্তব্য ব্যবহার করে গ্রাফের সংলগ্নতা তালিকা তৈরি করুন
একটি ফাংশন dfs() সংজ্ঞায়িত করুন। এটি x লাগবে, নির্বাচন করুন
যদি x দেখা যায়, তাহলে
- রিটার্ন 0
দেখা হিসাবে x চিহ্নিত করুন
উত্তর :=0
যদি চয়ন সত্য হয়, তাহলে
- উত্তর :=উত্তর + জনসংখ্যা[x]
adj[x]-এ প্রতিটি প্রতিবেশীর জন্য, করুন
- উত্তর :=ans + dfs(প্রতিবেশী, বেছে নেওয়ার বিপরীত)
উত্তর ফেরত দিন
প্রধান পদ্ধতি থেকে নিম্নলিখিতগুলি করুন:
x :=dfs(0, True)
সর্বোচ্চ x এবং (জনসংখ্যার যোগফল) - x)

আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -

উদাহরণ

from collections import defaultdict
class Solution:
   def solve(self, source, dest, population):
      adj = defaultdict(list)
      for a, b in zip(source, dest):
         adj[a].append(b)
         adj[b].append(a)

      seen = set()

      def dfs(x, choose):
         if x in seen:
            return 0
         seen.add(x)
         ans = 0
         if choose:
            ans += population[x]
         for neighbor in adj[x]:
            ans += dfs(neighbor, not choose)
         return ans

      x = dfs(0, True)
      return max(x, sum(population) - x)
     
ob = Solution()
source = [2, 2, 1, 1]
dest = [1, 3, 4, 0]
population = [6, 8, 4, 3, 5]
print(ob.solve(source, dest, population))

ইনপুট

[2, 2, 1, 1], [1, 3, 4, 0], [6, 8, 4, 3, 5]