Skip to content

1600. Throne Inheritance 👎

  • Time:
  • Space: 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
class ThroneInheritance {
 public:
  ThroneInheritance(string kingName) : kingName(kingName) {}

  void birth(string parentName, string childName) {
    family[parentName].push_back(childName);
  }

  void death(string name) {
    dead.insert(name);
  }

  vector<string> getInheritanceOrder() {
    vector<string> ans;
    dfs(kingName, ans);
    return ans;
  }

 private:
  unordered_set<string> dead;
  unordered_map<string, vector<string>> family;
  string kingName;

  void dfs(const string& name, vector<string>& ans) {
    if (!dead.contains(name))
      ans.push_back(name);
    if (!family.contains(name))
      return;

    for (const string& child : family[name])
      dfs(child, ans);
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
class ThroneInheritance {
  public ThroneInheritance(String kingName) {
    this.kingName = kingName;
  }

  public void birth(String parentName, String childName) {
    family.putIfAbsent(parentName, new ArrayList<>());
    family.get(parentName).add(childName);
  }

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

  public List<String> getInheritanceOrder() {
    List<String> ans = new ArrayList<>();
    dfs(kingName, ans);
    return ans;
  }

  private Set<String> dead = new HashSet<>();
  private Map<String, List<String>> family = new HashMap<>();
  private String kingName;

  private void dfs(final String name, List<String> ans) {
    if (!dead.contains(name))
      ans.add(name);
    if (!family.containsKey(name))
      return;

    for (final String child : family.get(name))
      dfs(child, ans);
  }
}