Leetcode 1376

// for this question we know it is tree structure so we dont need visited array, simply go down the tree would be good.

class Solution {
    public int numOfMinutes(int n, int headID, int[] manager, int[] informTime) {
        // build the graph 
        List<List<Integer>> graph = new ArrayList<>();
        for(int i = 0; i < n; i ++){
            graph.add(new ArrayList<>());
        }

        for(int i = 0; i < n; i ++){
            if (manager[i] != -1) {
                graph.get(manager[i]).add(i);
            }
        }

        // do the bfs
        Queue<int[]> q = new LinkedList<>();
        q.add(new int[]{headID,informTime[headID]});
        int res = 0;
        while(!q.isEmpty()){
            int[] curr = q.poll();
            res = Math.max(res,curr[1]);
            for(int next : graph.get(curr[0])){
                q.add(new int[]{next,curr[1] + informTime[next]});
            }
        }
        return res;
    }
}