Maximum Employees to Be Invited to a Meeting LeetCode solution in Java

1
class Solution {
2
  public int maximumInvitations(int[] favorite) {
3
    List<List<Integer>> graph = new ArrayList<>();
4
    for (int i = 0; i < favorite.length; i++) {
5
      graph.add(new ArrayList<>());
6
    }
7

8
    int answer = 0;
9

10
    List<List<Integer>> pairs = new ArrayList<>();
11
    for (int i = 0; i < favorite.length; i++) {
12
      if (i == favorite[favorite[i]]) {
13
        if (i < favorite[i]) {
14
          List<Integer> pair = new ArrayList<>();
15
          pair.add(i);
16
          pair.add(favorite[i]);
17
          pairs.add(pair);
18
        }
19
      } else {
20
        graph.get(favorite[i]).add(i);
21
      }
22
    }
23

24
    boolean[] visited = new boolean[favorite.length];
25
    for (List<Integer> pair : pairs) {
26
      answer += dfs(graph, pair.get(0), visited) + dfs(graph, pair.get(1), visited);
27
    }
28

29
    int[] counter = new int[favorite.length];
30
    int[] round = new int[favorite.length];
31

32
    int rnd = 1;
33

34
    int circleMax = 0;
35

36
    for (int i = 0; i < favorite.length; i++) {
37
      if (visited[i]) {
38
        continue;
39
      }
40
      if (round[i] != 0) {
41
        continue;
42
      }
43

44
      int cnt = 1;
45
      int j = i;
46
      while (counter[j] == 0) {
47
        counter[j] = cnt;
48
        round[j] = rnd;
49
        j = favorite[j];
50
        cnt++;
51
      }
52
      if (round[j] == rnd) {
53
        circleMax = Math.max(circleMax, cnt - counter[j]);
54
      }
55
      rnd++;
56
    }
57
    return Math.max(circleMax, answer);
58
  }
59

60
  private int dfs(List<List<Integer>> graph, int node, boolean[] visited) {
61
    visited[node] = true;
62
    int max = 0;
63
    for (int neighbor : graph.get(node)) {
64
      max = Math.max(max, dfs(graph, neighbor, visited));
65
    }
66
    return max + 1;
67
  }
68
}