参加会议的最多员工数【LC2127】
一个公司准备组织一场会议，邀请名单上有 n 位员工。公司准备了一张 圆形 的桌子，可以坐下 任意数目 的员工。
员工编号为 0 到 n - 1 。每位员工都有一位 喜欢 的员工，每位员工 当且仅当 他被安排在喜欢员工的旁边，他才会参加会议。每位员工喜欢的员工 不会 是他自己。
给你一个下标从 0 开始的整数数组 favorite ，其中 favorite[i] 表示第 i 位员工喜欢的员工。请你返回参加会议的 最多员工数目 。
思路：拓扑排序
- 内向基环树概念：从i向favorite[i]连边，可以得到一张有向图。由于每个大小为k的连通块都有k个点和k边，所以每个连通块必定有且仅有一个环，且由于每个点的出度均为 1，这样的有向图又叫做内向基环树
- 本题中有两种基环树
长度为2时，圆桌上可以放置多个长度等于2的环，及其最长链
长度大于2时，圆桌上只能放置一个长度大于2的环
因为相邻员工都需要有一位喜欢的员工
长度等于2的环内两位员工互相喜欢，在其边上可以再增加最长链【贪心，获得最多员工】，最长链的末尾又可以添加其他长度为2的环【结果1】
长度大于2的环内无法再添加其他员工【结果2】
最终答案为结果1和结果2的最大值
实现
可以使用拓扑排序找到基环和数值，并记录每个节点的最长链，计算两种内向基环树对应的结果
通过一次拓扑排序，可以「剪掉」所有树枝。因为拓扑排序后，树枝节点的入度均为 0，基环节点的入度均为 1。这样就可以将基环和树枝区分开，从而简化后续处理流程：
如果要遍历基环，可以从入度为 1的节点出发，遍历其余入度为 1 的节点。
如果要遍历树枝，可以以基环与树枝的连接处为起点，顺着反图来遍历树枝，从而将问题转化成一个树形问题。
作者：灵茶山艾府
链接：https://leetcode.cn/problems/maximum-employees-to-be-invited-to-a-meeting/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
class Solution { public int maximumInvitations(int[] favorite) { int n = favorite.length; int[] deg = new int[n]; for (int f : favorite) { deg[f]++; // 统计基环树每个节点的入度 } int[] maxDepth = new int[n]; Deque<Integer> q = new ArrayDeque<>(); for (int i = 0; i < n; i++) { if (deg[i] == 0) { q.add(i); } } while (!q.isEmpty()) { // 拓扑排序，剪掉图上所有树枝 int x = q.poll(); int y = favorite[x]; // x 只有一条出边 maxDepth[y] = maxDepth[x] + 1; if (--deg[y] == 0) { q.add(y); } } int maxRingSize = 0, sumChainSize = 0; for (int i = 0; i < n; i++) { if (deg[i] == 0) continue; // 遍历基环上的点 deg[i] = 0; // 将基环上的点的入度标记为 0，避免重复访问 int ringSize = 1; // 基环长度 for (int x = favorite[i]; x != i; x = favorite[x]) { deg[x] = 0; // 将基环上的点的入度标记为 0，避免重复访问 ringSize++; } if (ringSize == 2) { // 基环长度为 2 sumChainSize += maxDepth[i] + maxDepth[favorite[i]] + 2; // 累加两条最长链的长度 } else { maxRingSize = Math.max(maxRingSize, ringSize); // 取所有基环长度的最大值 } } return Math.max(maxRingSize, sumChainSize); } } 作者：灵茶山艾府 链接：https://leetcode.cn/problems/maximum-employees-to-be-invited-to-a-meeting/ 来源：力扣（LeetCode） 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
复杂度
时间复杂度：O ( n )
空间复杂度：O ( n )
