[Mdfs] lc690. 员工的重要性(dfs+bfs+离线询问+问题拓展+基础题)

1. 题目来源

链接：690. 员工的重要性

题单：

• 无

2. 题目解析

简单题目，直接 dfs 遍历子树每个节点，累加起来对应的值即可。

拓展：

• 如果有许多查询情况呢？涉及到离线查询。
• 那么需要找到根节点。
  • 如何找根？用一个 set 去维护一下，如果当前节点没有父节点，则为根节点。
• dfs 遍历得到每个节点作为根节点时，子树的重要值总和。
  • 这个需要在回溯的时候进行累加，并非向下递归的时候累加，这个需要注意。

当然，bfs 写法也非常直观，不赘述。

---

• 时间复杂度：$O(n)$
• 空间复杂度：$O(1)$

---

dfs

class Solution {
public:int getImportance(vector<Employee*> employees, int id) {unordered_map<int, Employee*> g;for (auto e : employees) g[e->id] = e;auto dfs = [&](auto&& dfs, int u) -> int {int res = g[u]->importance;for (auto e : g[u]->subordinates) res += dfs(dfs, e);return res;};return dfs(dfs, id);}
};

---

/*
// Definition for Employee.
class Employee {
public:int id;int importance;vector<int> subordinates;
};
*/class Solution {
public:int getImportance(vector<Employee*> employees, int id) {unordered_map<int, vector<int>> g;unordered_map<int, int> um;for (auto e : employees) {um[e->id] = e->importance;for (auto ne : e->subordinates) g[e->id].push_back(ne);}int res = 0;queue<int> q;q.push(id);while (!q.empty()) {int u = q.front(); q.pop();res += um[u];for (int v : g[u]) q.push(v);}return res;}
};

---

拓展：

/*
// Definition for Employee.
class Employee {
public:int id;int importance;vector<int> subordinates;
};
*/class Solution {
public:int getImportance(vector<Employee*> employees, int id) {unordered_map<int, vector<int>> g;unordered_map<int, int> um;set<int> S;for (auto e : employees) {S.insert(e->id);um[e->id] = e->importance;for (auto ne : e->subordinates) g[e->id].push_back(ne), S.erase(ne);}auto dfs = [&](auto&& dfs, int u, int fa) -> void {for (auto e : g[u]) {dfs(dfs, e, u);}if (fa > 0) um[fa] += um[u];};dfs(dfs, *S.begin(), -1);return um[id];}
};