# 1376. Time Needed to Inform All Employees
Link: https://leetcode.com/problems/time-needed-to-inform-all-employees/
###### tags: `Leetcode` `Medium` `DFS`
## 思路
### 思路一 top down dfs $O(N)$
首先建tree，然后dfs搜寻
### 思路二 bottom up dfs （省了一个建map的空间）$O(N^2)$
参考[这里](https://leetcode.com/problems/time-needed-to-inform-all-employees/discuss/532560/JavaC%2B%2BPython-DFS)
先想象出一个tree，然后对于每一个node来说，一个一个往上找，把informtime累加起来，做完之后把它的manager设成-1，这样再碰到这个node，就不会再加一遍informtime了
遍历所有node，每一个都这样做，最后得到的最大值就是答案
## Code
### 思路一 top down dfs

class Solution {
    public int numOfMinutes(int n, int headID, int[] manager, int[] informTime) {
        //map build tree
        //key manager value array of subordinates
        Map<Integer, List<Integer>> graph = new HashMap<Integer, List<Integer>>();
        int head = 0;
        for(int i=0;i<manager.length;i++){
            if(!graph.containsKey(manager[i])){
                graph.put(manager[i], new ArrayList<Integer>());
            }
            graph.get(manager[i]).add(i);
        }
        
        return dfs(headID, informTime, graph);
    }
    private int dfs(int head, int[] informTime,  Map<Integer, List<Integer>> graph){
        int max = 0;
        if(!graph.containsKey(head)) return max;
        else{
            for(int e:graph.get(head)){
                max = Math.max(max, dfs(e, informTime, graph));
            }
            return max+informTime[head];
        }
    }
}

### 思路二 bottom up dfs
java

class Solution {
    public int numOfMinutes(int n, int headID, int[] manager, int[] informTime) {
        int ans = 0;
        for(int i=0;i<manager.length;i++){
            ans = Math.max(ans, dfs(i, informTime, manager));
        }
        return ans;
    }
    private int dfs(int cur, int[] informTime, int[] manager){
        if(manager[cur]!=-1){
            informTime[cur] += dfs(manager[cur], informTime, manager);
            manager[cur]=-1;
        }
        return informTime[cur];
    }
}

c++

class Solution {
public:
    int numOfMinutes(int n, int headID, vector<int>& manager, vector<int>& informTime) {
        int ans = 0;
        for(int i=0; i<n; i++){
            ans = max(ans, dfs(i, manager, informTime));
        }
        return ans;
    }
    int dfs(int e, vector<int>& manager, vector<int>& informTime){
        if(manager[e]!=-1){
            informTime[e]+=dfs(manager[e], manager, informTime);
            manager[e]=-1;
        }
        return informTime[e];
    }
};