โปรแกรมหาลำดับสืบสังเคราะห์ในครอบครัวใน Python

ปัญหา

ครอบครัวมีสมาชิกหลายรุ่น มีการเกิดและตาย หัวหน้าครอบครัวคือคนอายุมากที่สุด ต้องการฟังก์ชัน birth(parent, child), death(name), inheritance() คืนลำดับสืบสังเคราะห์ปัจจุบัน (DFS preorder ข้ามผู้ตาย)

ตัวอย่าง

Paul → Zach, Jesse; Jesse → Ursula, Ryan, Thea; Paul ตาย → ลำดับ [Zach, Jesse, Ursula, Ryan, Thea]; Zach ตาย → [Jesse, Ursula, Ryan, Thea]

ขั้นตอนการแก้ปัญหา

1. family := defaultdict(list), head := head_name, dead := set()
2. birth(p, c): family[p].append(c)
3. death(name): dead.add(name)
4. inheritance(): DFS จาก head ข้ามคนใน dead เก็บลำดับ

การนำไปใช้งาน (Python)

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']