# Maximum Employees to Be Invited to a Meeting
**Difficulty:** HARD
[External](https://leetcode.com/problems/maximum-employees-to-be-invited-to-a-meeting)
Canonical: https://scaleengineer.com/dsa/problems/maximum-employees-to-be-invited-to-a-meeting
**Algorithms:** [Depth-First Search](https://scaleengineer.com/algorithms/depth-first-search), [Topological Sort](https://scaleengineer.com/algorithms/topological-sort)
**Data structures:** Graph
**Companies:** [Barclays](https://scaleengineer.com/companies/barclays), [SAP](https://scaleengineer.com/companies/sap)
---
## Problem
A company is organizing a meeting and has a list of `n` employees, waiting to be invited. They have arranged for a large **circular** table, capable of seating **any number** of employees.

The employees are numbered from `0` to `n - 1`. Each employee has a **favorite** person and they will attend the meeting **only if** they can sit next to their favorite person at the table. The favorite person of an employee is **not** themself.

Given a **0-indexed** integer array `favorite`, where `favorite[i]` denotes the favorite person of the `ith` employee, return _the **maximum number of employees** that can be invited to the meeting_.

**Example 1:**

![](https://assets.glich.co/dsa/maximum-employees-to-be-invited-to-a-meeting/image0.png) 

**Input:** favorite = [2,2,1,2]
**Output:** 3
**Explanation:**
The above figure shows how the company can invite employees 0, 1, and 2, and seat them at the round table.
All employees cannot be invited because employee 2 cannot sit beside employees 0, 1, and 3, simultaneously.
Note that the company can also invite employees 1, 2, and 3, and give them their desired seats.
The maximum number of employees that can be invited to the meeting is 3. 

**Example 2:**

**Input:** favorite = [1,2,0]
**Output:** 3
**Explanation:** 
Each employee is the favorite person of at least one other employee, and the only way the company can invite them is if they invite every employee.
The seating arrangement will be the same as that in the figure given in example 1:
- Employee 0 will sit between employees 2 and 1.
- Employee 1 will sit between employees 0 and 2.
- Employee 2 will sit between employees 1 and 0.
The maximum number of employees that can be invited to the meeting is 3.

**Example 3:**

![](https://assets.glich.co/dsa/maximum-employees-to-be-invited-to-a-meeting/image1.png) 

**Input:** favorite = [3,0,1,4,1]
**Output:** 4
**Explanation:**
The above figure shows how the company will invite employees 0, 1, 3, and 4, and seat them at the round table.
Employee 2 cannot be invited because the two spots next to their favorite employee 1 are taken.
So the company leaves them out of the meeting.
The maximum number of employees that can be invited to the meeting is 4.

**Constraints:**

* `n == favorite.length`
* `2 <= n <= 105`
* `0 <= favorite[i] <= n - 1`
* `favorite[i] != i`

# Approaches
## Naive Path Tracing
This approach directly simulates the process of finding cycles and chains by tracing paths from each node. It identifies all cycles in the graph. For cycles of length greater than two, the maximum length is a candidate for the answer. For cycles of length two, it forms larger groups by finding all chains of employees that lead to the two nodes in the cycle. This is done by repeatedly traversing from every other node.
**Time:** O(n^2). Finding all cycles can be done in O(n). However, for each of the O(n) possible 2-cycles, finding the longest chains by iterating through all O(n) other nodes and tracing their paths (which can be O(n) long) results in a complexity of at least O(n^2). · **Space:** O(n), where n is the number of employees. This space is used for the `visited` array and the hash map for path tracing.
**Pros:** Conceptually straightforward, as it directly models the path-tracing process.; Does not require complex graph algorithms like topological sorting.
**Cons:** Highly inefficient due to repeated computations.; The nested loops for finding chains for each 2-cycle lead to a poor time complexity, making it infeasible for large inputs.
### Explanation
The core idea is to treat the `favorite` array as a directed graph where an edge exists from `i` to `favorite[i]`. Since each employee has exactly one favorite, each node has an out-degree of one. Such a graph is a collection of components, each consisting of a cycle with trees pointing towards it.

This approach first finds all cycles by starting a traversal from each unvisited node. During a traversal, it keeps track of the path. If it encounters a node already on the current path, a cycle is found. The length of the largest cycle with more than 2 nodes is recorded.

Separately, it considers all 2-cycles. For each pair of employees `(u, v)` that are each other's favorite, it tries to find the longest chain of employees ending at `u` and the longest chain ending at `v`. This is done by iterating through every other employee `j` and tracing their favorite path to see if it terminates at `u` or `v`. The total number of employees for all such 2-cycle groups is summed up. 

The final answer is the maximum of the largest cycle found (if > 2) and the total sum from all 2-cycle groups.
### Algorithm
*   **Initialization**: Create a `visited` array to keep track of nodes whose component has been processed. Initialize `max_len = 0`.
*   **Iterate and Trace**: Loop through each employee `i` from `0` to `n-1`.
    *   If `i` has not been visited, start a trace from `i`.
    *   Follow the `favorite` pointers: `i -> favorite[i] -> favorite[favorite[i]] -> ...`.
    *   Use a hash map to store the nodes encountered in the current trace and their distance from the starting node `i`.
    *   If a node is encountered that is already in the current trace map, a cycle is detected.
*   **Process Cycles**: 
    *   Calculate the cycle length. If it's greater than 2, update `max_len = max(max_len, cycle_length)`.
    *   Mark all nodes in the traced path as visited.
*   **Handle 2-Cycles**: The above process only finds the largest single cycle. A separate logic is needed for the arrangement involving 2-cycles. We can find all 2-cycles (`u`, `v` where `favorite[u]=v` and `favorite[v]=u`).
*   **Find Chains (Inefficiently)**: For each 2-cycle (`u`, `v`), iterate through all other nodes `j`. Trace the path from `j` until it hits a cycle node. If it hits `u` or `v`, record the chain length. Find the maximum chain length for `u` and `v` respectively.
*   **Calculate Total**: Sum up the sizes of all these 2-cycle groups (`2 + chain_u + chain_v`). Let this be `total_2_cycle_sum`.
*   **Result**: The answer is `max(max_len, total_2_cycle_sum)`.

## Graph Traversal with Topological Sort
This efficient approach correctly identifies the two types of optimal arrangements: either one large cycle of length `k > 2`, or a collection of all 2-cycles, each extended with the longest possible chains of employees. It uses a graph traversal algorithm that runs in linear time.

First, it processes all the 'tree' portions of the graph using a topological sort-like method (Kahn's algorithm). This efficiently calculates the lengths of the longest chains leading to each node. The nodes that remain after this process are the ones that form cycles.

Then, it iterates through the remaining cycle nodes, finds each cycle, and calculates the potential number of invitees. For cycles of length greater than 2, the number is simply the cycle's length. For 2-cycles, it's the sum of the lengths of the two nodes plus their pre-calculated longest chains. The maximum of these two scenarios gives the answer.
**Time:** O(n). Each step (building in-degree, topological sort, and cycle processing) involves visiting each node and edge a constant number of times. · **Space:** O(n) for storing the in-degree, longest chain lengths, visited array, and the queue.
**Pros:** Optimal O(n) time complexity, which passes for large constraints.; Efficiently handles the graph structure by separating tree and cycle components.; Correctly identifies and solves the two distinct cases for maximal groups.
**Cons:** The implementation is more complex than a naive approach.; Requires understanding of graph components, in-degrees, and topological sorting.
### Explanation
This approach provides an optimal O(n) solution. It starts by calculating the in-degree of each node in the graph representation. Nodes with an in-degree of 0 are the starting points of chains (leaves of the trees pointing to cycles).

A queue is initialized with these leaf nodes. We process these nodes in a way similar to topological sorting. For each processed node `u`, we find its favorite `v` and update the length of the longest chain ending at `v`. This is done by `longest_chain[v] = max(longest_chain[v], longest_chain[u] + 1)`. We then decrement the in-degree of `v`. This process effectively 'prunes' all the tree structures from the graph, and the `longest_chain` array stores the lengths of the longest chains ending at the cycle nodes.

After this, we are left with only the cycle nodes (those with `indegree > 0`). We iterate through all nodes one last time. If we find an unvisited cycle node, we traverse the cycle it belongs to, determine its length, and mark its nodes as visited. 

If the cycle's length is `k > 2`, we update our `max_k_cycle` result. If the length is 2, we find the two nodes `u` and `v` and add their total group size, `longest_chain[u] + longest_chain[v]`, to a `sum_2_cycles` variable. The final answer is the maximum of `max_k_cycle` and `sum_2_cycles`.

```java
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;

class Solution {
    public int maximumInvitations(int[] favorite) {
        int n = favorite.length;
        int[] indegree = new int[n];
        for (int f : favorite) {
            indegree[f]++;
        }

        // longest_chain[i] will store the length of the longest chain ending at node i.
        int[] longest_chain = new int[n];
        Arrays.fill(longest_chain, 1);
        Queue<Integer> q = new LinkedList<>();
        for (int i = 0; i < n; i++) {
            if (indegree[i] == 0) {
                q.offer(i);
            }
        }

        // Topological sort to find longest chains for each node
        while (!q.isEmpty()) {
            int u = q.poll();
            int v = favorite[u];
            // The chain to v can be extended by the chain from u
            longest_chain[v] = Math.max(longest_chain[v], longest_chain[u] + 1);
            indegree[v]--;
            if (indegree[v] == 0) {
                q.offer(v);
            }
        }

        int max_k_cycle = 0; // Max length of a cycle with k > 2
        int sum_2_cycles = 0; // Sum of all employees in 2-cycle groups
        boolean[] visited = new boolean[n];

        // Process nodes that are part of cycles
        for (int i = 0; i < n; i++) {
            if (indegree[i] > 0 && !visited[i]) {
                int cycle_len = 0;
                int curr = i;
                // Find the length of the cycle
                while (!visited[curr]) {
                    visited[curr] = true;
                    cycle_len++;
                    curr = favorite[curr];
                }

                if (cycle_len == 2) {
                    // For a 2-cycle, the total group size is the sum of their chains + 2.
                    // Our longest_chain array already includes the nodes themselves.
                    // So, (chain_u - 1) + (chain_v - 1) + 2 = chain_u + chain_v.
                    // We need to find the two nodes. i and favorite[i] are the pair.
                    sum_2_cycles += longest_chain[i] + longest_chain[favorite[i]];
                } else {
                    // For cycles with k > 2, they cannot be extended with chains.
                    max_k_cycle = Math.max(max_k_cycle, cycle_len);
                }
            }
        }

        return Math.max(max_k_cycle, sum_2_cycles);
    }
}
```
### Algorithm
*   **Graph Analysis**: The problem can be modeled as a functional graph where each node has an out-degree of 1. Such a graph consists of components, each with exactly one cycle and some trees leading to it.
*   **Build In-degree Array**: Compute the in-degree for each node. `indegree[i]` will be the number of employees who favor employee `i`.
*   **Find Chains with Topological Sort**: Use a Kahn's algorithm-like approach. Initialize a queue with all nodes having an in-degree of 0 (these are leaves of the trees). Process the queue to traverse the trees.
    *   Maintain a `longest_chain` array, initialized to 1. 
    *   When processing a node `u` from the queue, consider its favorite `v = favorite[u]`. Update `longest_chain[v] = max(longest_chain[v], longest_chain[u] + 1)`. Then, decrement `indegree[v]`. If `indegree[v]` becomes 0, add `v` to the queue.
*   **Identify Cycle Nodes**: After the topological sort process, any node `i` with `indegree[i] > 0` is part of a cycle.
*   **Process Cycles**: Iterate through all nodes `i` from `0` to `n-1`.
    *   If a node `i` is a cycle node (i.e., `indegree[i] > 0`) and has not been visited yet (by this cycle-processing step):
        *   Trace the cycle starting from `i` to find its length.
        *   If the cycle length is 2 (a pair `u, v`), add `longest_chain[u] + longest_chain[v]` to a running sum `sum_2_cycles`. Note that `longest_chain[x]` includes the node `x` itself, so the number of people is `(longest_chain[u]-1) + (longest_chain[v]-1) + 2`, which simplifies to `longest_chain[u] + longest_chain[v]`.
        *   If the cycle length is greater than 2, update a variable `max_k_cycle` with the maximum length found so far.
        *   Mark all nodes in the found cycle as visited to avoid reprocessing.
*   **Final Result**: The answer is `max(max_k_cycle, sum_2_cycles)`.

# Solutions
### Java

```java
class Solution {
public
  int maximumInvitations(int[] favorite) {
    return Math.max(maxCycle(favorite), topologicalSort(favorite));
  }
private
  int maxCycle(int[] fa) {
    int n = fa.length;
    boolean[] vis = new boolean[n];
    int ans = 0;
    for (int i = 0; i < n; ++i) {
      if (vis[i]) {
        continue;
      }
      List<Integer> cycle = new ArrayList<>();
      int j = i;
      while (!vis[j]) {
        cycle.add(j);
        vis[j] = true;
        j = fa[j];
      }
      for (int k = 0; k < cycle.size(); ++k) {
        if (cycle.get(k) == j) {
          ans = Math.max(ans, cycle.size() - k);
        }
      }
    }
    return ans;
  }
private
  int topologicalSort(int[] fa) {
    int n = fa.length;
    int[] indeg = new int[n];
    int[] dist = new int[n];
    Arrays.fill(dist, 1);
    for (int v : fa) {
      indeg[v]++;
    }
    Deque<Integer> q = new ArrayDeque<>();
    for (int i = 0; i < n; ++i) {
      if (indeg[i] == 0) {
        q.offer(i);
      }
    }
    int ans = 0;
    while (!q.isEmpty()) {
      int i = q.pollFirst();
      dist[fa[i]] = Math.max(dist[fa[i]], dist[i] + 1);
      if (--indeg[fa[i]] == 0) {
        q.offer(fa[i]);
      }
    }
    for (int i = 0; i < n; ++i) {
      if (i == fa[fa[i]]) {
        ans += dist[i];
      }
    }
    return ans;
  }
}

```

### CPP

```cpp
class Solution {
public:
  int maximumInvitations(vector<int> &favorite) {
    return max(maxCycle(favorite), topologicalSort(favorite));
  }
  int maxCycle(vector<int> &fa) {
    int n = fa.size();
    vector<bool> vis(n);
    int ans = 0;
    for (int i = 0; i < n; ++i) {
      if (vis[i])
        continue;
      vector<int> cycle;
      int j = i;
      while (!vis[j]) {
        cycle.push_back(j);
        vis[j] = true;
        j = fa[j];
      }
      for (int k = 0; k < cycle.size(); ++k) {
        if (cycle[k] == j) {
          ans = max(ans, (int)cycle.size() - k);
          break;
        }
      }
    }
    return ans;
  }
  int topologicalSort(vector<int> &fa) {
    int n = fa.size();
    vector<int> indeg(n);
    vector<int> dist(n, 1);
    for (int v : fa)
      ++indeg[v];
    queue<int> q;
    for (int i = 0; i < n; ++i)
      if (indeg[i] == 0)
        q.push(i);
    while (!q.empty()) {
      int i = q.front();
      q.pop();
      dist[fa[i]] = max(dist[fa[i]], dist[i] + 1);
      if (--indeg[fa[i]] == 0)
        q.push(fa[i]);
    }
    int ans = 0;
    for (int i = 0; i < n; ++i)
      if (i == fa[fa[i]])
        ans += dist[i];
    return ans;
  }
};

```

### Python

```python
class Solution:
    def maximumInvitations(self, favorite: List[int]) -> int: def max_cycle(fa: List[int]) -> int: n = len(fa) vis = [False] * n ans = 0 for i in range(n): if vis[i]: continue cycle = [] j = i while not vis[j]: cycle . append(j) vis[j] = True j = fa[j] for k, v in enumerate(cycle): if v == j: ans = max(ans, len(cycle) - k) break return ans def topological_sort(fa: List[int]) -> int: n = len(fa) indeg = [0] * n dist = [1] * n for v in fa: indeg[v] += 1 q = deque(i for i, v in enumerate(indeg) if v == 0) while q: i = q . popleft() dist[fa[i]] = max(dist[fa[i]], dist[i] + 1) indeg[fa[i]] -= 1 if indeg[fa[i]] == 0: q . append(fa[i]) return sum(dist[i] for i, v in enumerate(fa) if i == fa[fa[i]]) return max(max_cycle(favorite), topological_sort(favorite))

```