मान लीजिए, एक परिवार है जिसमें विभिन्न पीढ़ियों के सदस्य हैं। जैसे परिवार में एक पिता, उसके बच्चे, और उनकी दादी हैं। लेकिन हर परिवार में जन्म और मृत्यु होती है।
परिवार का सबसे बड़ा सदस्य मुखिया माना जाता है। तो, जब 'मुखिया' सदस्य मर जाता है, तो उनका सीधा उत्तराधिकारी या उनके बच्चे मुखिया बन जाते हैं। हम तीन फंक्शन इम्प्लीमेंट करते हैं, पहला तब उपयोग किया जाता है जब परिवार में कोई बच्चा पैदा होता है। फंक्शन पैरेंट का नाम और बच्चे का नाम इनपुट के रूप में लेता है और उन्हें रिकॉर्ड में जोड़ता है।
दूसरा फंक्शन तब उपयोग किया जाता है जब कोई मृत्यु होती है। यह मृत परिवार के सदस्य का नाम इनपुट के रूप में लेता है और उन्हें रिकॉर्ड से हटा देता है।
तीसरा फंक्शन उत्तराधिकार का क्रम देता है। जब भी इसे बुलाया जाता है तो उत्तराधिकार का वर्तमान क्रम प्रिंट होता है।
उदाहरण के लिए, इनपुट के एक सेट के लिए; हमें उत्तराधिकार का क्रम ढूंढना है। तो, यदि इनपुट का क्रम है: birth, birth, birth, birth, birth, death, inheritance, death, inheritance, तो आउटपुट होगा: ['Zach', 'Jesse', 'Ursula', 'Ryan', 'Thea'] ['Jesse', 'Ursula', 'Ryan', 'Thea']
सबसे पहले परिवार का मुखिया पॉल है।
फिर पॉल के बच्चे हुए जिनका नाम क्रमशः जैच और जेसी है।
जेसी के फिर तीन बच्चे हुए; उर्सुला, रयान, और थिया, उर्सुला सबसे बड़ी और थिया सबसे छोटी।
फिर पॉल मर जाता है। उत्तराधिकार का क्रम है ['Zach', 'Jesse', 'Ursula', 'Ryan', 'Thea']।
फिर जैच मर जाता है, उत्तराधिकार का क्रम बन जाता है ['Jesse', 'Ursula', 'Ryan', 'Thea']।
समाधान के चरण
family :=एक नया मैप जिसमें मान के रूप में सूचियां होंhead :=परिवार का वर्तमान मुखियाdead :=एक सेटbirth()फंक्शन परिभाषित करें जोp_name,c_nameलेता है:c_nameकोfamily[p_name]के अंत में डालें
death()फंक्शन परिभाषित करें जोnameलेता है:dead.add(name)
inheritance()फंक्शन परिभाषित करें:ans := []depth_search(head)ansवापस करें
depth_search()फंक्शन परिभाषित करें जोcurrentलेता है:- यदि
currentdeadमें नहीं है:currentकोansके अंत में डालें
family[current]में प्रत्येकchildके लिए:depth_search(child)
- यदि
उदाहरण
बेहतर समझ के लिए निम्नलिखित कार्यान्वयन देखें:
from collections import defaultdict
class Solution:
def __init__(self, head_name):
self.family = defaultdict(list)
self.head = head_name
self.dead = set()
def birth(self, p_name, c_name):
self.family[p_name].append(c_name)
def death(self, name):
self.dead.add(name)
def inheritance(self):
self.ans = []
self.depth_search(self.head)
return self.ans
def depth_search(self, current):
if current not in self.dead:
self.ans.append(current)
for child in self.family[current]:
self.depth_search(child)
ob = Solution('Paul')
ob.birth('Paul', 'Zach')
ob.birth('Paul', 'Jesse')
ob.birth('Jesse', 'Ursula')
ob.birth('Jesse', 'Ryan')
ob.birth('Jesse', 'Thea')
ob.death('Paul')
print(ob.inheritance())
ob.death('Zach')
print(ob.inheritance())
इनपुट
ob = Solution('Paul')
ob.birth('Paul', 'Zach')
ob.birth('Paul', 'Jesse')
ob.birth('Jesse', 'Ursula')
ob.birth('Jesse', 'Ryan')
ob.birth('Jesse', 'Thea')
ob.death('Paul')
print(ob.inheritance())
ob.death('Zach')
print(ob.inheritance())
आउटपुट
['Zach', 'Jesse', 'Ursula', 'Ryan', 'Thea']
['Jesse', 'Ursula', 'Ryan', 'Thea']