Throne Inheritance

// Accepted solution for LeetCode #1600: Throne Inheritance
class ThroneInheritance {
    private String king;
    private Set<String> dead = new HashSet<>();
    private Map<String, List<String>> g = new HashMap<>();
    private List<String> ans = new ArrayList<>();

    public ThroneInheritance(String kingName) {
        king = kingName;
    }

    public void birth(String parentName, String childName) {
        g.computeIfAbsent(parentName, k -> new ArrayList<>()).add(childName);
    }

    public void death(String name) {
        dead.add(name);
    }

    public List<String> getInheritanceOrder() {
        ans.clear();
        dfs(king);
        return ans;
    }

    private void dfs(String x) {
        if (!dead.contains(x)) {
            ans.add(x);
        }
        for (String y : g.getOrDefault(x, List.of())) {
            dfs(y);
        }
    }
}

/**
 * Your ThroneInheritance object will be instantiated and called as such:
 * ThroneInheritance obj = new ThroneInheritance(kingName);
 * obj.birth(parentName,childName);
 * obj.death(name);
 * List<String> param_3 = obj.getInheritanceOrder();
 */

// Accepted solution for LeetCode #1600: Throne Inheritance
type ThroneInheritance struct {
	king string
	dead map[string]bool
	g map[string][]string
}


func Constructor(kingName string) ThroneInheritance {
	return ThroneInheritance{kingName, map[string]bool{}, map[string][]string{}}
}


func (this *ThroneInheritance) Birth(parentName string, childName string)  {
	this.g[parentName] = append(this.g[parentName], childName)
}


func (this *ThroneInheritance) Death(name string)  {
	this.dead[name] = true
}


func (this *ThroneInheritance) GetInheritanceOrder() (ans []string) {
	var dfs func(string)
	dfs = func(x string) {
		if !this.dead[x] {
			ans = append(ans, x)
		}
		for _, y := range this.g[x] {
			dfs(y)
		}
	}
	dfs(this.king)
	return
}


/**
 * Your ThroneInheritance object will be instantiated and called as such:
 * obj := Constructor(kingName);
 * obj.Birth(parentName,childName);
 * obj.Death(name);
 * param_3 := obj.GetInheritanceOrder();
 */

# Accepted solution for LeetCode #1600: Throne Inheritance
class ThroneInheritance:

    def __init__(self, kingName: str):
        self.king = kingName
        self.dead = set()
        self.g = defaultdict(list)

    def birth(self, parentName: str, childName: str) -> None:
        self.g[parentName].append(childName)

    def death(self, name: str) -> None:
        self.dead.add(name)

    def getInheritanceOrder(self) -> List[str]:
        def dfs(x: str):
            x not in self.dead and ans.append(x)
            for y in self.g[x]:
                dfs(y)

        ans = []
        dfs(self.king)
        return ans


# Your ThroneInheritance object will be instantiated and called as such:
# obj = ThroneInheritance(kingName)
# obj.birth(parentName,childName)
# obj.death(name)
# param_3 = obj.getInheritanceOrder()

// Accepted solution for LeetCode #1600: Throne Inheritance
use std::collections::HashMap;
use std::collections::HashSet;

struct ThroneInheritance {
    root: String,
    nodes: HashMap<String, Vec<String>>,
    dead: HashSet<String>,
}

impl ThroneInheritance {
    fn new(root: String) -> Self {
        let nodes = HashMap::new();
        let dead = HashSet::new();
        ThroneInheritance { root, nodes, dead }
    }

    fn birth(&mut self, parent_name: String, child_name: String) {
        self.nodes.entry(parent_name).or_default().push(child_name);
    }

    fn death(&mut self, name: String) {
        self.dead.insert(name);
    }

    fn get_inheritance_order(&self) -> Vec<String> {
        let mut res = vec![];
        self.dfs(&self.root, &mut res);
        res
    }

    fn dfs(&self, name: &str, all: &mut Vec<String>) {
        if !self.dead.contains(name) {
            all.push(name.to_string())
        }
        for child in self.nodes.get(name).unwrap_or(&vec![]) {
            self.dfs(child, all);
        }
    }
}

#[test]
fn test() {
    let mut t = ThroneInheritance::new("king".to_string());
    t.birth("king".to_string(), "andy".to_string());
    t.birth("king".to_string(), "bob".to_string());
    t.birth("king".to_string(), "catherine".to_string());
    t.birth("andy".to_string(), "matthew".to_string());
    t.birth("bob".to_string(), "alex".to_string());
    t.birth("bob".to_string(), "asha".to_string());
    let order = t.get_inheritance_order();
    assert_eq!(
        order,
        vec_string![
            "king",
            "andy",
            "matthew",
            "bob",
            "alex",
            "asha",
            "catherine"
        ]
    );
    t.death("bob".to_string());
    let order = t.get_inheritance_order();
    assert_eq!(
        order,
        vec_string!["king", "andy", "matthew", "alex", "asha", "catherine"]
    );
}

// Accepted solution for LeetCode #1600: Throne Inheritance
class ThroneInheritance {
    private king: string;
    private dead: Set<string> = new Set();
    private g: Map<string, string[]> = new Map();

    constructor(kingName: string) {
        this.king = kingName;
    }

    birth(parentName: string, childName: string): void {
        this.g.set(parentName, this.g.get(parentName) || []);
        this.g.get(parentName)!.push(childName);
    }

    death(name: string): void {
        this.dead.add(name);
    }

    getInheritanceOrder(): string[] {
        const ans: string[] = [];
        const dfs = (x: string) => {
            if (!this.dead.has(x)) {
                ans.push(x);
            }
            for (const y of this.g.get(x) || []) {
                dfs(y);
            }
        };
        dfs(this.king);
        return ans;
    }
}

/**
 * Your ThroneInheritance object will be instantiated and called as such:
 * var obj = new ThroneInheritance(kingName)
 * obj.birth(parentName,childName)
 * obj.death(name)
 * var param_3 = obj.getInheritanceOrder()
 */