পাইথনে ট্রি থেকে স্পেশাল নোডের সংখ্যা বের করা (ইউনিক কালার সাবট্রি)

একটি n-ary ট্রি দেওয়া আছে এডজেসেন্সি লিস্ট tree হিসেবে (রুট = tree[0])। প্রতিটি নোডের একটি কালার আছে color লিস্টে। একটি নোড N স্পেশাল হবে যদি তার সাবট্রির সব নোডের কালার ইউনিক (Unique) হয়। স্পেশাল নোডের সংখ্যা বের করতে হবে।

উদাহরণ: tree=[[1,2],[0],[0,3],[2]], colors=[1,2,1,1] → আউটপুট 2।

সমাধানের ধাপসমূহ (DFS + সেট মার্জিং)

result := 0
dfs(node, prev) ফাংশন:
- colors = {color[node]} (সেট)।
- প্রতিটি চাইল্ডের জন্য (প্রিভ ছাড়া):
  - child_colors = dfs(child, node)
  - যদি colors ও child_colors দুটোই নন-এম্পটি হয় এবং ইন্টারসেকশন থাকে, তবে colors = None (স্পেশাল নয়)।
  - অন্যথায় ছোট সেট বড় সেটে মার্জ করুন (Small-to-Large merging)।
- যদি colors নন-এম্পটি থাকে, result++।
- colors রিটার্ন করুন।
dfs(0, -1) কল করে result রিটার্ন করুন।

পাইথন কোড উদাহরণ

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
        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
        dfs(0, -1)
        return self.result

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]