Chương trình tìm nút đặc biệt trong cây trong Python

Cho cây n-ary (danh sách kề tree) và mảng color. Nút i có con/cha trong tree[i], màu color[i]. Nút N "đặc biệt" nếu mọi nút trong cây con gốc N có màu duy nhất (không trùng). Đếm số nút đặc biệt.

Ví dụ: tree=[[1,2],[0],[0,3],[2]], colors=[1,2,1,1] → 2.

Giải pháp

DFS post-order trả về tập màu của cây con:

• dfs(node, prev): trả về set màu cây con gốc node, hoặc None nếu không đặc biệt
• Khởi tạo colors = {color[node]}
• Duyệt con: child_colors = dfs(child, node)
• Nếu colors và child_colors giao nhau không rỗng → colors = None
• Ngược lại hợp nhất set nhỏ vào set lớn (small-to-large merging)
• Nếu colors không None: result++

Ví dụ minh họa

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]))

Đầu vào

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

Đầu ra

2