पायथन में ट्री में विशेष नोड्स ज्ञात करने का प्रोग्राम

मान लीजिए हमारे पास 'tree' नामक मानों की एक 2D सूची है जो एक n-ary ट्री का प्रतिनिधित्व करती है और 'color' नामक मानों की एक अन्य सूची है। ट्री को एक आसन्न सूची के रूप में दर्शाया गया है और इसकी जड़ tree[0] है।

i-th नोड की विशेषताएं:

• tree[i] इसके बच्चे और माता-पिता हैं।

• color[i] इसका रंग है।

हम एक नोड N को "विशेष" कहते हैं यदि उस उपट्री में हर नोड जिसकी जड़ N पर है, का एक अद्वितीय रंग है। तो हमारे पास यह ट्री है, हमें विशेष नोड्स की संख्या ज्ञात करनी है।

इसलिए, यदि इनपुट tree = [[1,2], [0], [0,3], [2]] और colors = [1, 2, 1, 1] जैसा है, तो आउटपुट 2 होगा।

हल करने के चरण

• result := 0

• dfs(0, -1)

• result लौटाएं

• check_intersection() फ़ंक्शन परिभाषित करें। यह colors, child_colors लेगा

  • यदि colors की लंबाई < child_colors की लंबाई, तो

    • colors में प्रत्येक c के लिए, यदि c, child_colors में है तो True लौटाएं

  • अन्यथा, child_colors में प्रत्येक c के लिए, यदि c, colors में है तो True लौटाएं

• dfs() फ़ंक्शन परिभाषित करें। यह node, prev लेगा

  • colors := {color[node]}

  • tree[node] में प्रत्येक child के लिए, करें

    • यदि child, prev के समान नहीं है, तो

      • child_colors := dfs(child, node)

      • यदि colors और child_colors खाली नहीं हैं, तो

        • यदि check_intersection(colors, child_colors) शून्येतर है, तो colors := null

        • अन्यथा, यदि colors की लंबाई < child_colors की लंबाई, तो child_colors |= colors और colors := child_colors

        • अन्यथा, colors |= child_colors

      • अन्यथा, colors := null

  • यदि colors खाली नहीं है, तो result := result + 1

  • colors लौटाएं

उदाहरण

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