পাইথনের একটি গাছে বিশেষ নোডগুলি খুঁজে বের করার জন্য প্রোগ্রাম

ধরুন আমাদের কাছে 'ট্রি' নামক মানের একটি 2D তালিকা রয়েছে যা একটি n-ary গাছকে প্রতিনিধিত্ব করে এবং 'রঙ' নামক মানের আরেকটি তালিকা। গাছটিকে একটি সংলগ্ন তালিকা হিসাবে উপস্থাপন করা হয় এবং এর মূল হল গাছ[0]।

i-th নোড -

• গাছ[i] তার সন্তান এবং পিতামাতা।

• রঙ[i] এর রঙ।

আমরা একটি নোডকে N "বিশেষ" বলি যদি সাবট্রির প্রতিটি নোড যার মূল N এ থাকে তার একটি অনন্য রঙ থাকে। সুতরাং আমাদের এই গাছটি আছে, আমাদের বিশেষ নোডের সংখ্যা খুঁজে বের করতে হবে।

So, if the input is like tree = [
   [1,2],
   [0],
   [0,3],
   [2]
]

রং =[1, 2, 1, 1], তাহলে আউটপুট হবে 2।

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

• ফলাফল :=0

• dfs(0, -1)

• ফেরত ফলাফল

• একটি ফাংশন সংজ্ঞায়িত করুন check_intersection()। এটি রং লাগবে, চাইল্ড_রং

  • যদি (রঙ) এর দৈর্ঘ্য <(child_colors) এর দৈর্ঘ্য, তাহলে

    • প্রতিটি c রঙের জন্য, করুন

      • চাইল্ড_রঙে c যদি অ-শূন্য হয়, তাহলে

        • রিটার্ন ট্রু

  • অন্যথায়,

    • চাইল্ড_রঙে প্রতিটি c-এর জন্য করুন

      • c যদি চাইল্ড_রঙে থাকে, তাহলে

        • রিটার্ন ট্রু

• একটি ফাংশন dfs() সংজ্ঞায়িত করুন। এটি নোড নেবে, পূর্বে

  • রং :={রঙ[নোড]}

  • গাছের [নোড] প্রতিটি শিশুর জন্য, করুন

    • যদি সন্তান আগের মত না হয়, তাহলে

      • child_colors :=dfs(চাইল্ড, নোড)

      • যদি রং এবং চাইল্ড_রঙ খালি না হয়, তাহলে

        • যদি চেক_ছেদ (রঙ, চাইল্ড_রং) অ-শূন্য হয়, তাহলে

          • রং :=শূন্য

        • অন্যথায়,

          • যদি (রঙ) এর দৈর্ঘ্য <(child_colors) এর দৈর্ঘ্য, তাহলে,

            • চাইল্ড_রং :=চাইল্ড_রং বা রং

            • রং :=চাইল্ড_রঙ

          • অন্যথায়,

            • রং :=রং বা চাইল্ড_রঙ

      • অন্যথায়,

        • রং :=শূন্য

    • যদি রং খালি না হয়, তাহলে

      • ফলাফল :=ফলাফল + 1

    • রিটার্ন রং

উদাহরণ

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

import collections
class Solution:
   def solve(self, tree, color):
      self.result = 0
      def dfs(node, prev):
         colors = {color[node]}
         for child in tree[node]:
            if child != prev:
               child_colors = dfs(child, node)
               if colors and child_colors:
                  if self.check_intersection(colors, child_colors):
                     colors = None
                  else:
                     if len(colors) < len(child_colors):
                        child_colors |= colors
                        colors = child_colors
                     else:
                        colors |= child_colors
                  else:
                     colors = None
            if colors:
               self.result += 1
            return colors
         dfs(0, -1)
         return self.result
      def check_intersection(self, colors, child_colors):
         if len(colors) < len(child_colors):
            for c in colors:
               if c in child_colors:
                  return True
         else:
            for c in child_colors:
               if c in colors:
                  return True
ob = Solution()
print(ob.solve( [
   [1,2],
   [0],
   [0,3],
   [2]
], [1, 2, 1, 1]))

ইনপুট

[
   [1,2],
   [0],
   [0,3],
   [2]
], [1, 2, 1, 1]

আউটপুট

2