पायथन का उपयोग करके समान लेबल वाले उप-वृक्ष में नोड्स की संख्या खोजने का कार्यक्रम

मान लीजिए कि हमारे पास n नोड्स वाला एक रूटेड सामान्य ट्री है, जिसके नोड्स 0 से n-1 तक गिने जाते हैं। प्रत्येक नोड में लोअरकेस अंग्रेजी अक्षर वाला एक लेबल होता है। लेबल्स को लेबल एरे में इनपुट के रूप में दिया जाता है, जहां लेबल्स [i] में ith नोड के लिए लेबल होता है। पेड़ को किनारे की सूची द्वारा दर्शाया जाता है जहां प्रत्येक किनारे ई में [यू, वी] प्रतिनिधित्व करता है कि आप माता-पिता हैं और वी बच्चा है। हमें आकार n की एक सरणी A ढूंढनी है, जो i

तो, अगर इनपुट पसंद है

यहाँ n =5 और लेबल ="ccaca"

तब आउटपुट [3, 2, 1, 1, 1] होगा क्योंकि रूट में एक ही लेबल वाले तीन वंशज हैं, नोड 1 में दो वंशज हैं, और अन्य सभी उस लेबल को धारण करते हैं।

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -

• E :=दी गई किनारे की सूची से ग्राफ़ बनाएं

• N :=प्रत्येक नोड संख्या और उसके संगत लेबल वाला नक्शा

• R :=आकार n की सूची और 0 से भरें

• फ़ंक्शन r() को परिभाषित करें। इसमें नी लगेगा

• सी:=एक कुंजी की आवृत्ति धारण करने के लिए एक नक्शा

• ई [नी] में प्रत्येक ई के लिए, करें

  • E[e]

    . से ni हटाएं

  • C

    . में r(e) अपडेट करें

• N[ni] को C

  . में अपडेट करें

• आर[नी] :=सी[एन[नी]]

• वापसी सी

• मुख्य विधि से कॉल करें r(0)

• वापसी आर

आइए बेहतर समझ पाने के लिए निम्नलिखित कार्यान्वयन देखें -

उदाहरण

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]