โปรแกรมหาโหนดพิเศษในต้นไม้ใน Python

คำอธิบายโจทย์

ให้ tree (adjacency list) และ color ของแต่ละโหนด โหนด N เป็น "special" ถ้าทุกโหนดใน subtree ของ N มีสี unique (ไม่ซ้ำ) หาจำนวน special nodes

ตัวอย่าง

tree = [[1,2],[0],[0,3],[2]], colors = [1,2,1,1] → 2

วิธีแก้ปัญหา

DFS Post-order + Set Merging (Small-to-Large):

1. DFS จาก root (0) ส่งคืน set ของสีใน subtree
2. merge child sets เข้า parent set (small-to-large optimization)
3. ถ้าพบสีซ้ำระหว่าง parent และ child → subtree นี้ไม่ special (colors = None)
4. นับโหนดที่ colors ไม่เป็น None

โค้ด Python

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
            return False
        
        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]

เอาต์พุต

2