leetcode/Problem1443/Solution.java at master · gorthitk/leetcode · GitHub

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
35
36
37
38
39
40
41
42
43
44


import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

class Solution
{
    public int minTime(int n, int[][] edges, List<Boolean> hasApple)
    {
        final Map<Integer, List<Integer>> graph = new HashMap<>();
        for (int i = 0; i < edges.length; i++)
        {
            graph.computeIfAbsent(edges[i][0], k -> new ArrayList<>()).add(edges[i][1]);
            graph.computeIfAbsent(edges[i][1], k -> new ArrayList<>()).add(edges[i][0]);
        }
        return _compute(0, graph, hasApple, new boolean[n]);
    }

    private int _compute(int index, Map<Integer, List<Integer>> graph, List<Boolean> hasApple, boolean[] visited)
    {
        if (!graph.containsKey(index))
        {
            return 0;
        }
        visited[index] = true;
        int count = 0;
        for (int child : graph.get(index))
        {
            if (visited[child])
            {
                continue;
            }
            count += _compute(child, graph, hasApple, visited);
            if (hasApple.get(child))
            {
                hasApple.set(index, true);
                count += 2;
            }
        }
        return count;
    }
}