千问 LeetCode 2127.参加会议的最多员工数 public int maximumInvitations(int[] favorite)

这道题是图论中的经典问题考察的是基环树的处理。 题目分析1. 建模将员工看作图的节点favorite[i] 表示从节点 i 指向节点 favorite[i] 的一条有向边。2. 图的结构由于每个节点出度为 1这个图由若干个基环树组成。基环树是指一个环环上的每个节点可能挂着一棵树树枝指向环。3. 目标找到一个最大的节点集合使得集合中每个节点的 favorite 也在集合中。 关键观察这个问题有两种可能的最优解结构1. 大环如果存在一个长度大于 2 的环那么整个环上的节点都可以被选中。因为环上每个节点的 favorite 都在环上。2. 双向配对 链如果存在长度为 2 的环即 A 喜欢 BB 喜欢 A那么 A 和 B 可以互相选择。此外可以分别从 A 和 B 出发沿着反向边即喜欢 A 的人喜欢 B 的人延伸出最长的链。这种结构可以形成 链A - A B 2 的环记录最大环的长度。3. 处理长度 2 的环对于每个长度为 2 的环计算从两个节点出发能延伸出的最长链的长度然后将所有这种结构的长度相加。4. 返回最大值返回上述两种情况的最大值。 Java 代码实现import java.util.*;class Solution {public int maximumInvitations(int[] favorite) {int n favorite.length;// 构建反向图用于计算链的长度List reverseGraph new ArrayList();for (int i 0; i ());}for (int i 0; i queue new LinkedList();for (int i 0; i cycle new ArrayList();int cur i;while (!visited[cur]) {visited[cur] true;cycle.add(cur);cur favorite[cur];}int cycleSize cycle.size();if (cycleSize 2) {// 长度为 2 的环计算最长链int a cycle.get(0);int b cycle.get(1);// 从 a 出发不经过 b能走多远int lenA getLongestChain(a, b, reverseGraph);// 从 b 出发不经过 a能走多远int lenB getLongestChain(b, a, reverseGraph);sumOfPairs 2 lenA lenB;} else {// 长度大于 2 的环maxCycleSize Math.max(maxCycleSize, cycleSize);}}return Math.max(maxCycleSize, sumOfPairs);}// 计算从 start 出发不经过 avoid能走的最长链长度private int getLongestChain(int start, int avoid, List reverseGraph) {int maxLen 0;for (int next : reverseGraph.get(start)) {if (next ! avoid) {maxLen Math.max(maxLen, 1 getLongestChain(next, avoid, reverseGraph));}}return maxLen;}} 算法步骤详解1. 构建反向图reverseGraph[i] 存储所有喜欢员工 i 的员工列表。2. 拓扑排序通过 Kahn 算法找出所有不在环上的节点。入度为 0 的节点一定不在环上将其移除后可能会产生新的入度为 0 的节点继续这个过程。3. 识别环剩下的节点都在环上。遍历这些节点找出每个环。4. 分类处理* 如果环长度为 2计算从两个节点出发能延伸出的最长链累加到 sumOfPairs。* 如果环长度大于 2更新 maxCycleSize。5. 返回结果返回 max(maxCycleSize, sumOfPairs)。 复杂度分析* 时间复杂度O(n)。拓扑排序 O(n)找环 O(n)计算最长链 O(n)。* 空间复杂度O(n)。用于存储图、入度数组、访问标记等。