千问 LeetCode 2127.参加会议的最多员工数 public int maximumInvitations(int[] favorite)
这道题是图论中的经典问题，考察的是基环树的处理。
🧠 题目分析
1. 建模：将员工看作图的节点，favorite[i] 表示从节点 i 指向节点 favorite[i] 的一条有向边。
2. 图的结构：由于每个节点出度为 1，这个图由若干个基环树组成。基环树是指一个环，环上的每个节点可能挂着一棵树（树枝指向环）。
3. 目标：找到一个最大的节点集合，使得集合中每个节点的 favorite 也在集合中。
🔍 关键观察
这个问题有两种可能的最优解结构：
1. 大环：如果存在一个长度大于 2 的环，那么整个环上的节点都可以被选中。因为环上每个节点的 favorite 都在环上。
2. 双向配对 + 链：如果存在长度为 2 的环（即 A 喜欢 B，B 喜欢 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)。用于存储图、入度数组、访问标记等。