पायथन में एक पेड़ में विशेष नोड्स का पता लगाने का कार्यक्रम

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

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

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

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

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
- अगर लंबाई (रंग) <लंबाई (child_colors) है, तो
  - रंगों में प्रत्येक c के लिए, करें
    - अगर c चाइल्ड_कलर्स में गैर-शून्य है, तो
      - सही लौटें
- अन्यथा,
  - प्रत्येक c के लिए child_colors में, करें
    - अगर c चाइल्ड_कलर्स में मौजूद है, तो
      - सही लौटें
फ़ंक्शन को परिभाषित करें dfs() । यह नोड लेगा, पिछला
- रंग :={रंग [नोड]}
- पेड़ में प्रत्येक बच्चे के लिए[नोड], करें
  - अगर बच्चा पिछला जैसा नहीं है, तो
    - Child_colors :=dfs (बच्चा, नोड)
    - अगर रंग और बच्चे_रंग खाली नहीं हैं, तो
      - अगर check_intersection(colors,child_colors) गैर-शून्य है, तो
        
        रंग :=शून्य
      - अन्यथा,
        
        यदि लंबाई (रंगों) <की लंबाई (child_colors) है, तो,
        
        Child_colors :=child_colors OR कलर्स
        
        रंग :=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]