Largest Circular Seating with Favorite Neighbors

### Problem Employees are numbered from `0` through `n - 1`. Employee `i` names a different employee, `favorite[i]`, and will attend only if seated next to that person. Choose a subset of employees and arrange them around one circular table. Return the greatest number who can attend with every invited employee's preference satisfied. ```cpp class Solution { public: int maximumInvitations(vector<int>& favorite); }; ``` ### Examples **Example 1:** ```text favorite = [1,0,3,2] Output: 4 Explanation: Seat 0,1,2,3 around the circle, preserving both mutual-favorite pairs. ``` **Example 2:** ```text favorite = [1,2,3,0] Output: 4 Explanation: The four-cycle itself gives a valid circular order. ``` ### Constraints - `2 <= favorite.length <= 10^5`. - `0 <= favorite[i] < favorite.length`; `favorite[i] != i`. ### Clarifying Questions An employee needs only their own favorite adjacent; the preference need not be mutual. Each seat has two neighbors. ```hint Inspect the structure Why can a mutual-favorite pair attach chains on both ends, while a longer directed cycle cannot? ``` ### Reasoning checkpoints - Satisfy each invited person's own adjacency requirement, even when the preference is not mutual. - Use one circular seating arrangement and account for the two neighboring seats available to each person. - Prove the attendance count is achievable and that a larger invited subset cannot be seated. ### Optional extensions How could you also return a seating order that attains the maximum attendance?