Pythonでツリー内の特別なノードを見つけるプログラム

n-aryツリーを表す「tree」と呼ばれる値の2Dリストと、「color」と呼ばれる別の値のリストがあるとします。ツリーは隣接リストとして表され、そのルートはtree[0]です。

i番目のノードの特性-

• tree[i]はその子であり親です。

• color[i]はその色です。

ルートがNにあるサブツリー内のすべてのノードが一意の色を持っている場合、ノードNを「特別」と呼びます。このツリーがあるので、特別なノードの数を調べる必要があります。

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

  • （colors）の長さ<（child_colors）の長さの場合、

    • 色のcごとに、実行します

      • child_colorsのcがゼロ以外の場合、

        • Trueを返す

  • それ以外の場合

    • child_colorsのcごとに、実行します

      • cがchild_colorsに存在する場合、

        • Trueを返す

• 関数dfs（）を定義します。これはノードを取ります、前へ

  • 色：={color [node]}

  • tree [node]の子ごとに、実行

    • 子供が前と同じでない場合は、

      • child_colors：=dfs（child、node）

      • 色とchild_colorsが空でない場合は、

        • check_intersection（colors、child_colors）がゼロ以外の場合、

          • 色：=null

        • それ以外の場合

          • （colors）の長さ<（child_colors）の長さの場合、

            • child_colors：=child_colorsまたはcolors

            • 色：=child_colors

          • それ以外の場合

            • 色：=色またはchild_colors

      • それ以外の場合

        • 色：=null

    • 色が空でない場合は、

      • 結果：=結果+ 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]

出力

2