A problem at which I stared for an hour

Problem: [LC2127 - Maximum Employees to Be Invited to a Meeting](https://leetcode.com/problems/maximum-employees-to-be-invited-to-a-meeting/) 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: ##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. ## Solution If an employee A has a favourite person, let's say employee B, and vice versa. Then we can put them together. Then we can put an employee, let's say C, whose favourite person is A on the left hand side of A. Then put an employee, let's say D, whose favourite person is C next to C. If we do the same thing for employee B, then we can have two ways to extend. Therefore, we can first look for the interdependent nodes, in this case, A & B. ``` if (a[a[i]] == i) { // TODO: calculate the left chain and the right chain } ``` Starting from node A and node B, we perform dfs to calculate the maximum nodes of the left chain and the right chain. Then we could invite $left + right + 2$ people. ``` function<int(int)> dfs = [&](int u) { if (depth[u] != -1) return depth[u]; int res = 0; for (int x : inv[u]) res = max(res, dfs(x)); return depth[u] = res + 1; }; ``` However, it would fail for the input [1,2,0] because it will output $0$ instead of $3$. In this case, we need to take care of the cyclic dependency. We need to run another dfs function for each node and check if there is a cyclic dependency. If the visited node is the entry node, then we know there is a cycle here. Then we could invite them also. ``` function<tuple<int, int, int>(int)> dfs2 = [&](int u)->tuple<int, int, int> { if (depth[u] != -1) { return { u, depth[u], 0 }; } depth[u] = 0; auto [entry, d, isCyclic] = dfs2(a[u]); if (isCyclic) { return { entry, d, 1 }; } depth[u] = d + 1; return { entry, depth[u], u == entry }; }; ``` The final answer is simple the maximum number of the result of case 1 and case 2. Here's the full solution. ``` class Solution { public: int maximumInvitations(vector<int>& a) { int n = a.size(); vector<int> depth(n, -1); vector<vector<int>> inv(n); for (int i = 0 ; i < n; i++) inv[a[i]].push_back(i); // check interdependent nodes + longest left & right chain function<int(int)> dfs = [&](int u) { if (depth[u] != -1) return depth[u]; int res = 0; for (int x : inv[u]) res = max(res, dfs(x)); return depth[u] = res + 1; }; int mx1 = 0, mx2 = 0; for (int i = 0; i < n; i++) { if (depth[i] != -1) continue; if (a[a[i]] == i) { depth[i] = depth[a[i]] = 0; int left = 0, right = 0; for (int x : inv[i]) if (x != a[i]) left = max(left, dfs(x)); for (int x : inv[a[i]]) if (x != a[i]) right = max(right, dfs(x)); mx1 += left + right + 2; } } // check cyclic dependency function<tuple<int, int, int>(int)> dfs2 = [&](int u)->tuple<int, int, int> { if (depth[u] != -1) { return { u, depth[u], 0 }; } depth[u] = 0; auto [entry, d, isCyclic] = dfs2(a[u]); if (isCyclic) { return { entry, d, 1 }; } depth[u] = d + 1; return { entry, depth[u], u == entry }; }; for (int i = 0; i < n; i++) { if (depth[i] != -1) continue; auto [entry, d, isCyclic] = dfs2(i); if (isCyclic) { mx2 = max(mx2, d); } } return max(mx1, mx2); } }; ```