图论5（Leetcode1376.通知所有员工所需的时间）

答案：

这是官方答案 我写的超时了 我不会树结构的存储 这里用了Map 学到了

class Solution {
    public int numOfMinutes(int n, int headID, int[] manager, int[] informTime) {
        Map<Integer,List<Integer>> g = new HashMap<Integer, List<Integer>>();
        for(int i=0;i<n;i++){
            g.putIfAbsent(manager[i],new ArrayList<Integer>());
            g.get(manager[i]).add(i);
        }
        return dfs(headID,informTime,g);
    }
    public int dfs(int cur, int[] informTime, Map<Integer, List<Integer>> g){
        int res = 0;
        for(int neighbor:g.getOrDefault(cur,new ArrayList<Integer>())){
            res = Math.max(res,dfs(neighbor, informTime, g));
        }
        return res + informTime[cur];
    }
}

这是我自己写的 我感觉逻辑是对的 但是超时

class Solution {
    public int numOfMinutes(int n, int headID, int[] manager, int[] informTime) {
        int[] time = new int[n];
        int x = 1;//统计已通知到的人数(1:head)
        Set<Integer> newInform = new HashSet<>();
        newInform.add(headID);
        time[headID]=0;
        while(x<n){
            Set<Integer> newInform2 = new HashSet<>();
            Iterator<Integer> iterator = newInform.iterator();
            while(iterator.hasNext()){
                int m = iterator.next();
                int t = informTime[m];
                int tAll = time[m];
                for(int i=0;i<n;i++){
                    if(manager[i]==m){
                        time[i] = tAll + t;
                        newInform2.add(i);
                        x++;
                    }
                }
            }
            newInform = newInform2;
        }
        int max = 0;
        for(int i=0;i<n;i++){
            if(time[i]>max){
                max = time[i];
            }
        }
        return max;

    }

}