Maximum Employees to Be Invited to a Meeting LeetCode solution in C++

1
class Solution {
2
 public:
3
  vector<vector<int>> rev;
4
  vector<int> es, sizeOfTwo;
5
  int N, ans1, ans2;
6
  void dfs(vector<int> &depth, int cur, int d) {
7
    if (depth[cur] > 0) {
8
      if (d - depth[cur] == 2) sizeOfTwo.push_back(cur);
9
      ans1 = max(ans1, d - depth[cur]);
10
      return;
11
    }
12
    if (depth[cur] != -1) return;
13
    depth[cur] = d;
14
    dfs(depth, es[cur], d + 1);
15
    depth[cur] = 0; // 0 means visited
16
  }
17
  void findAllCircules() {
18
    vector<int> depth(N, -1);
19
    for (int i = 0; i < N; i++) {
20
      if (depth[i] == -1) {
21
        dfs(depth, i, 1);
22
      }
23
    }
24
  }
25
  int dfs2(int cur, int except) {
26
    int ret = 1;
27
    int d = 0;
28
    for (auto nxt : rev[cur]) {
29
      if (nxt != except) {
30
        d = max(d, dfs2(nxt, except));
31
      }
32
    }
33
    return ret + d;
34
  }
35
  void expandSizeOfTwo() {
36
    for (auto i : sizeOfTwo) {
37
      int j = es[i];
38
      ans2 += dfs2(i, j);
39
      ans2 += dfs2(j, i);
40
    }
41
  }
42
  int maximumInvitations(vector<int> &favorite) {
43
    es = favorite;
44
    N = es.size(), ans1 = 0, ans2 = 0;
45
    rev.resize(N);
46
    for (int i = 0; i < N; i++) {
47
      rev[es[i]].push_back(i);
48
    }
49
    findAllCircules();
50
    expandSizeOfTwo();
51
    return max(ans1, ans2);
52
  }
53
};