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

Giả sử chúng ta có một danh sách 2D các giá trị được gọi là 'cây' đại diện cho một cây n-ary và một danh sách các giá trị khác được gọi là 'màu'. Cây được biểu diễn dưới dạng danh sách kề và gốc của nó là cây [0].

Các đặc điểm của nút thứ i -

• tree [i] là con và cha của nó.

• color [i] là màu của nó.

Chúng ta gọi một nút N là "đặc biệt" nếu mọi nút trong cây con có gốc ở N có một màu duy nhất. Vì vậy, chúng ta có cây này, chúng ta phải tìm ra số lượng các nút đặc biệt.

So, if the input is like tree = [
   [1,2],
   [0],
   [0,3],
   [2]
]

color =[1, 2, 1, 1], thì đầu ra sẽ là 2.

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• kết quả:=0

• dfs (0, -1)

• trả về kết quả

• Định nghĩa một hàm check_intersection (). Thao tác này sẽ có màu sắc, child_colors

  • nếu độ dài của (màu) <độ dài của (màu_ con) thì

    • đối với mỗi c trong màu sắc, làm

      • nếu c trong child_colors khác 0 thì

        • trả về True

  • nếu không,

    • đối với mỗi c trong child_colors, thực hiện

      • nếu c có trong màu con thì

        • trả về True

• Định nghĩa một hàm dfs (). Điều này sẽ chiếm nút, trước

  • màu sắc:={color [node]}

  • đối với mỗi phần tử con trong cây [node], thực hiện

    • nếu đứa trẻ không giống trước đó, thì

      • child_colors:=dfs (con, nút)

      • nếu màu sắc và màu con không trống, thì

        • nếu check_intersection (color, child_colors) khác 0 thì

          • màu sắc:=null

        • nếu không,

          • nếu độ dài của (màu sắc) <độ dài của (màu sắc con), thì,

            • child_colors:=child_colors HOẶC màu

            • màu sắc:=child_colors

          • nếu không,

            • màu sắc:=màu sắc HOẶC màu con

      • nếu không,

        • màu sắc:=null

    • nếu màu không trống thì

      • kết quả:=kết quả + 1

    • trả lại màu sắc

Ví dụ

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

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