Chương trình tìm thứ tự kế thừa trong gia đình trong Python

Mô phỏng thứ tự kế thừa ngai vàng/đầu gia tộc. Có 3 thao tác: birth(parent, child), death(name), inheritance() trả về danh sách kế thừa hiện tại (DFS pre-order, bỏ qua người đã mất).

Ví dụ: Paul là tổ trưởng. Paul sinh Zach, Jesse. Jesse sinh Ursula, Ryan, Thea. Paul mất → kế thừa: [Zach, Jesse, Ursula, Ryan, Thea]. Zach mất → [Jesse, Ursula, Ryan, Thea].

Giải thuật (Cây + DFS)

1. Dùng defaultdict(list) lưu con của mỗi người.
2. Set dead lưu người đã mất.
3. birth(p, c): thêm c vào family[p].
4. death(name): thêm vào dead.
5. inheritance(): DFS từ head, thêm vào kết quả nếu không trong dead.

Ví dụ minh họa

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())

Đầu vào

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())

Đầu ra

['Zach', 'Jesse', 'Ursula', 'Ryan', 'Thea'] ['Jesse', 'Ursula', 'Ryan', 'Thea']