Maximum Employees to Be Invited to a Meeting

Link

Description

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 i-th employee, return the maximum number of employees that can be invited to the meeting.

Example 1:

• 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:

• 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 <= 10^5
• 0 <= favorite[i] <= n - 1
• favorite[i] != i

Solution

See reference (Chinese).

Pseudotrees:

A pseudotree is a connected graph that slightly deviates from the strict definition of a tree. While a tree is a connected, acyclic graph with \(n\) vertices and \(n-1\) edges, a pseudotree has \(n\) vertices and \(n\) edges, introducing exactly one cycle into the structure. This singular cycle is what distinguishes a pseudotree from a tree. Despite the presence of this cycle, the graph remains minimally connected, meaning if any edge is removed, the graph will no longer be connected.

Characteristics:

• Singular Cycle: The defining characteristic of a pseudotree is the presence of exactly one cycle. This means there's precisely one path where you can start and end at the same vertex without traversing any edge more than once.
• Connectivity: A pseudotree remains connected, ensuring there's a path between any two vertices.
• Edge Count: With \(n\) vertices, a pseudotree has \(n\) edges, which is one more than a tree with the same number of vertices.

Pseudoforests:

A pseudoforest extends the concept of pseudotrees to a collection of disconnected graphs, where each component graph is a pseudotree. Therefore, a pseudoforest with \(k\) pseudotrees has \(n\) vertices and \(n+k\) edges, where each component pseudotree contains exactly one cycle.

Characteristics:

• Disjoint Pseudotrees: A pseudoforest is made up of multiple pseudotrees that are not connected to each other.
• Cycle Limit: Each component pseudotree in a pseudoforest contains exactly one cycle.

Directed Pseudotrees:

In directed graphs, pseudotrees can be categorized into in-trees and out-trees based on the direction of edges:

• In-Tree: Every vertex except for one (which lies on the cycle) has an in-degree of 1, meaning all edges direct towards the cycle or a path leading to the cycle.
• Out-Tree: Conversely, every vertex except for one has an out-degree of 1, indicating that all edges emanate from the cycle or lead away from it.

Code:

class Solution {
public:
    int maximumInvitations(vector<int>& favorite) {
        int n = favorite.size();
        vector<int> inDegree(n); // Count of how many people favor each employee
        for (int f : favorite) {
            inDegree[f]++;
        }

        queue<int> que; // Queue for topological sorting
        for (int i = 0; i < n; i++) {
            if (inDegree[i] == 0) { // Employees with no one favoring them are starting points
                que.push(i);
            }
        }

        vector<int> maxDepth(n); // Maximum depth from each employee to the end of their in-tree
        while (!que.empty()) {
            int current = que.front();
            que.pop();

            int next = favorite[current];
            maxDepth[next] = max(maxDepth[next], maxDepth[current] + 1); // Update max depth towards the cycle or root
            if (--inDegree[next] == 0) { // Prepare for the next layer if this was the last incoming edge
                que.push(next);
            }
        }

        int sumOfSpecialCircles = 0, regularCircle = 0;
        for (int i = 0; i < n; i++) {
            if (inDegree[i] > 0) { // Employees part of a cycle
                int circleSize = 1; // Start with the current employee
                inDegree[i] = 0; // Mark as processed
                for (int x = favorite[i]; x != i; x = favorite[x]) { // Traverse the cycle
                    circleSize++;
                    inDegree[x] = 0; // Mark as processed
                }

                if (circleSize == 2) { // Special case: 2-person cycle
                    sumOfSpecialCircles += 2 + maxDepth[i] + maxDepth[favorite[i]]; // Add the pair and their chains
                } else { // Regular cycle
                    regularCircle = max(regularCircle, circleSize); // Keep track of the largest cycle
                }
            }
        }

        return max(sumOfSpecialCircles, regularCircle); // Maximum of either special cycles with chains or a single large cycle
    }
};

Approach:

1. Initialization and In-Degree Calculation:
2. The inDegree vector is used to store the number of people who have each employee as their favorite. This is a crucial step to identify employees with no one favoring them, indicating the start points for a topological sort.

3. queue<int> que is initialized to store employees in the order they are to be processed in topological sorting.

4. Topological Sorting to Find 'In-Trees':

5. The algorithm employs a queue to perform a topological sort based on in-degrees. Employees with an in-degree of 0 (no one's favorite) are added to the queue as starting points.
6. In the context of pseudoforests, an employee with in-degree 0 can be seen as an isolated node or the end node of an "in-tree" where paths (indicating favoritism) lead inwards towards a cycle or another tree.

7. As employees are processed (removed from the queue), their favorite person's in-degree is decremented. If this decrement results in an in-degree of 0, that employee is then added to the queue. This step effectively performs a layer-by-layer traversal of the in-trees, calculating the maximum depth from the outermost layer towards the cycle or root.

8. Calculating Maximum Depth and Identifying Cycles:

9. maxDepth vector stores the maximum distance of each employee from the end of their in-tree, aiding in later calculations for employees involved in special 2-person cycles.

10. After the topological sort, the remaining employees with non-zero in-degrees are part of cycles. The algorithm then iterates through each employee to find these cycles and classify them.

11. Handling Special 2-Person Cycles:

12. A special case in this problem is a 2-person cycle, where each person is the favorite of the other. Such pairs can have additional people attached to them (forming chains that lead into this pair) but cannot be part of a larger cycle themselves.

13. For each 2-person cycle found, the algorithm calculates the sum of the maximum depths of the chains leading into each member of the pair (since both can invite their chains of admirers) and adds 2 (for the pair itself) to sumOfSpecialCircles.

14. Handling Regular Cycles:

15. For cycles larger than 2 persons, only the members of the cycle can be invited since inviting anyone outside the cycle (except in the special 2-person case) would break the condition of everyone sitting next to their favorite.

16. The algorithm keeps track of the largest such cycle with regularCircle.

17. Result Calculation:

18. The maximum number of invitations is the larger of sumOfSpecialCircles and regularCircle. This is because the meeting can either optimize for a series of connected 2-person cycles with their chains or a single large cycle, whichever is bigger.

19. Time complexity: \(O(n)\);

20. Space complexity: \(O(n)\).