পাইথন ব্যবহার করে একই লেবেল সহ সাব-ট্রিতে নোডের সংখ্যা খুঁজে বের করার প্রোগ্রাম

ধরুন আমাদের কাছে n নোড সহ একটি মূলযুক্ত সাধারণ গাছ আছে, যার নোডগুলি 0 থেকে n-1 পর্যন্ত সংখ্যাযুক্ত। প্রতিটি নোডে ছোট হাতের ইংরেজি অক্ষর সহ একটি লেবেল রয়েছে। লেবেলগুলি লেবেল অ্যারেতে ইনপুট হিসাবে দেওয়া হয়, যেখানে lables[i]-এ ith নোডের জন্য লেবেল থাকে। গাছটি প্রান্ত তালিকা দ্বারা প্রতিনিধিত্ব করা হয় যেখানে প্রতিটি প্রান্ত e এর [u,v] প্রতিনিধিত্ব করে u হল পিতামাতা এবং v হল শিশু। আমাদের n আকারের একটি অ্যারে খুঁজে বের করতে হবে, ith নোডের সাবট্রিতে i

সুতরাং, যদি ইনপুট মত হয়

এখানে n =5 এবং লেবেল =“ccaca”

তাহলে আউটপুট হবে [3, 2, 1, 1, 1] কারণ একই লেবেলের সাথে রুটের তিনটি বংশধর রয়েছে, নোড 1-এর দুটি বংশধর রয়েছে এবং অন্য সকলেই সেই লেবেলটি ধরে রেখেছে।

এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -

• E :=প্রদত্ত প্রান্ত তালিকা থেকে গ্রাফ তৈরি করুন

• N :=প্রতিটি নোড নম্বর এবং এর সংশ্লিষ্ট লেবেল ধারণকারী একটি মানচিত্র

• R :=n আকারের একটি তালিকা এবং 0

  দিয়ে পূরণ করুন

• একটি ফাংশন r() সংজ্ঞায়িত করুন। এটি নিবে

• C :=একটি কীর ফ্রিকোয়েন্সি ধরে রাখার জন্য একটি মানচিত্র

• E[ni]-এর প্রতিটি e-এর জন্য, করুন

  • E[e]

    থেকে ni মুছুন

  • C

    -এ r(e) আপডেট করুন

• C

  -এ N[ni] আপডেট করুন

• R[ni] :=C[N[ni]]

• C

  ফেরত দিন

• মূল পদ্ধতি থেকে r(0)

  কল করুন

• R

  ফেরত দিন

আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -

উদাহরণ

from collections import defaultdict, Counter
def solve(n, edges, labels):
   E = defaultdict(set)
   for f,t in edges:
      E[f].add(t)
      E[t].add(f)
   N = {i:e for i,e in enumerate(labels)}
   R = [0]*n
   def r(ni):
      C = Counter()
      for e in E[ni]:
         E[e].remove(ni)
         C.update(r(e))
      C.update((N[ni]))
      R[ni] = C[N[ni]]
      return C
   r(0)
   return R
n = 5
edges = [[0,1],[0,2],[1,3],[0,4]]
labels = "ccaca"
print(solve(n, edges, labels))

ইনপুট

5, [[0,1],[0,2],[1,3],[0,4]], "ccaca"

আউটপুট

[3, 2, 1, 1, 1]