Count Subtrees With Max Distance Between Cities LeetCode solution in Java

1
class Solution {
2
  public int[] countSubgraphsForEachDiameter(int n, int[][] edges) {
3

4
    ArrayList<Integer>[] graph = (ArrayList<Integer>[]) new ArrayList[n];
5
    for (int i = 0; i < n; i++) graph[i] = new ArrayList<>();
6

7
    for (int i = 0; i < edges.length; i++) {
8
      int u = edges[i][0];
9
      int v = edges[i][1];
10

11
      --u;
12
      --v;
13

14
      graph[u].add(v);
15
      graph[v].add(u);
16
    }
17

18
    int[] darr = new int[n - 1];
19

20
    for (int mask = 0; mask < (1 << (n)); mask++) {
21
      int d = getmax(mask, graph);
22

23
      if (d > 0) {
24
        darr[d - 1]++;
25
      }
26
    }
27

28
    return darr;
29
  }
30

31
  int getmax(int mask, ArrayList<Integer>[] graph) {
32

33
    int maxd = -1;
34

35
    for (int i = 0; i < 15; i++) {
36
      if ((mask & (1 << i)) != 0) {
37
        maxd = Math.max(maxd, dfs(i, graph, mask));
38
      }
39
    }
40

41
    return maxd;
42
  }
43

44
  int dfs(int node, ArrayList<Integer>[] graph, int mask) {
45

46
    Queue<Integer> q = new LinkedList<>();
47
    q.add(node);
48
    int dist = -1;
49
    int curr = mask;
50

51
    while (!q.isEmpty()) {
52
      dist++;
53

54
      for (int l = q.size() - 1; l >= 0; l--) {
55
        int z1 = q.peek();
56
        curr = curr ^ (1 << z1);
57
        q.remove();
58

59
        for (int z : graph[z1]) {
60
          if (((mask & (1 << z)) != 0) && ((curr & (1 << z)) != 0)) {
61
            q.add(z);
62
          }
63
        }
64
      }
65
    }
66

67
    if (curr != 0) {
68
      return -1;
69
    }
70

71
    return dist;
72
  }
73
}