Skip to content

2127. Maximum Employees to Be Invited to a Meeting 👍

  • Time: $O(n)$
  • Space: $O(n)$
 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
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
enum class State { kInit, kVisiting, kVisited };

class Solution {
 public:
  int maximumInvitations(vector<int>& favorite) {
    const int n = favorite.size();
    int sumComponentsLength = 0;  // the component: a -> b -> c <-> x <- y
    vector<vector<int>> graph(n);
    vector<int> inDegrees(n);
    vector<int> maxChainLength(n, 1);
    queue<int> q;

    // Build the graph.
    for (int i = 0; i < n; ++i) {
      graph[i].push_back(favorite[i]);
      ++inDegrees[favorite[i]];
    }

    // Perform topological sorting.
    for (int i = 0; i < n; ++i)
      if (inDegrees[i] == 0)
        q.push(i);

    while (!q.empty()) {
      const int u = q.front();
      q.pop();
      for (const int v : graph[u]) {
        if (--inDegrees[v] == 0)
          q.push(v);
        maxChainLength[v] = max(maxChainLength[v], 1 + maxChainLength[u]);
      }
    }

    for (int i = 0; i < n; ++i)
      if (favorite[favorite[i]] == i)
        // i <-> favorite[i] (the cycle's length = 2)
        sumComponentsLength += maxChainLength[i] + maxChainLength[favorite[i]];

    int maxCycleLength = 0;  // the cycle : a -> b -> c -> a
    vector<int> parent(n, -1);
    vector<bool> seen(n);
    vector<State> states(n);

    for (int i = 0; i < n; ++i)
      if (!seen[i])
        findCycle(graph, i, parent, seen, states, maxCycleLength);

    return max(sumComponentsLength / 2, maxCycleLength);
  }

 private:
  void findCycle(const vector<vector<int>>& graph, int u, vector<int>& parent,
                 vector<bool>& seen, vector<State>& states,
                 int& maxCycleLength) {
    seen[u] = true;
    states[u] = State::kVisiting;

    for (const int v : graph[u]) {
      if (!seen[v]) {
        parent[v] = u;
        findCycle(graph, v, parent, seen, states, maxCycleLength);
      } else if (states[v] == State::kVisiting) {
        // Find the cycle's length.
        int curr = u;
        int cycleLength = 1;
        while (curr != v) {
          curr = parent[curr];
          ++cycleLength;
        }
        maxCycleLength = max(maxCycleLength, cycleLength);
      }
    }

    states[u] = State::kVisited;
  }
};

 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
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
enum State { kInit, kVisiting, kVisited }

class Solution {
  public int maximumInvitations(int[] favorite) {
    final int n = favorite.length;
    int sumComponentsLength = 0; // the component: a -> b -> c <-> x <- y
    List<Integer>[] graph = new List[n];
    int[] inDegrees = new int[n];
    int[] maxChainLength = new int[n];
    Arrays.fill(maxChainLength, 1);

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

    // Build the graph.
    for (int i = 0; i < n; ++i) {
      graph[i].add(favorite[i]);
      ++inDegrees[favorite[i]];
    }

    // Perform topological sorting.
    Queue<Integer> q = IntStream.range(0, n)
                           .filter(i -> inDegrees[i] == 0)
                           .boxed()
                           .collect(Collectors.toCollection(ArrayDeque::new));

    while (!q.isEmpty()) {
      final int u = q.poll();
      for (final int v : graph[u]) {
        if (--inDegrees[v] == 0)
          q.offer(v);
        maxChainLength[v] = Math.max(maxChainLength[v], 1 + maxChainLength[u]);
      }
    }

    for (int i = 0; i < n; ++i)
      if (favorite[favorite[i]] == i)
        // i <-> favorite[i] (the cycle's length = 2)
        sumComponentsLength += maxChainLength[i] + maxChainLength[favorite[i]];

    int[] parent = new int[n];
    Arrays.fill(parent, -1);
    boolean[] seen = new boolean[n];
    State[] states = new State[n];

    for (int i = 0; i < n; ++i)
      if (!seen[i])
        findCycle(graph, i, parent, seen, states);

    return Math.max(sumComponentsLength / 2, maxCycleLength);
  }

  private int maxCycleLength = 0; // the cycle : a -> b -> c -> a

  private void findCycle(List<Integer>[] graph, int u, int[] parent, boolean[] seen,
                         State[] states) {
    seen[u] = true;
    states[u] = State.kVisiting;

    for (final int v : graph[u]) {
      if (!seen[v]) {
        parent[v] = u;
        findCycle(graph, v, parent, seen, states);
      } else if (states[v] == State.kVisiting) {
        // Find the cycle's length.
        int curr = u;
        int cycleLength = 1;
        while (curr != v) {
          curr = parent[curr];
          ++cycleLength;
        }
        maxCycleLength = Math.max(maxCycleLength, cycleLength);
      }
    }

    states[u] = State.kVisited;
  }
}

 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
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
from enum import Enum


class State(Enum):
  kInit = 0
  kVisiting = 1
  kVisited = 2


class Solution:
  def maximumInvitations(self, favorite: list[int]) -> int:
    n = len(favorite)
    sumComponentsLength = 0  # the component: a -> b -> c <-> x <- y
    graph = [[] for _ in range(n)]
    inDegrees = [0] * n
    maxChainLength = [1] * n

    # Build the graph.
    for i, f in enumerate(favorite):
      graph[i].append(f)
      inDegrees[f] += 1

    # Perform topological sorting.
    q = collections.deque([i for i, d in enumerate(inDegrees) if d == 0])

    while q:
      u = q.popleft()
      for v in graph[u]:
        inDegrees[v] -= 1
        if inDegrees[v] == 0:
          q.append(v)
        maxChainLength[v] = max(maxChainLength[v], 1 + maxChainLength[u])

    for i in range(n):
      if favorite[favorite[i]] == i:
        # i <-> favorite[i] (the cycle's length = 2)
        sumComponentsLength += maxChainLength[i] + maxChainLength[favorite[i]]

    maxCycleLength = 0  # Cycle: a -> b -> c -> a
    parent = [-1] * n
    seen = set()
    states = [State.kInit] * n

    def findCycle(u: int) -> None:
      nonlocal maxCycleLength
      seen.add(u)
      states[u] = State.kVisiting
      for v in graph[u]:
        if v not in seen:
          parent[v] = u
          findCycle(v)
        elif states[v] == State.kVisiting:
          # Find the cycle's length.
          curr = u
          cycleLength = 1
          while curr != v:
            curr = parent[curr]
            cycleLength += 1
          maxCycleLength = max(maxCycleLength, cycleLength)
      states[u] = State.kVisited

    for i in range(n):
      if i not in seen:
        findCycle(i)

    return max(sumComponentsLength // 2, maxCycleLength)