千问 LeetCode 2127.参加会议的最多员工数 Python3实现
这道题考察的是基环树（Pseudotree）的性质以及拓扑排序的应用。
🧠 核心思路
1. 图的结构：每个员工是一个节点，favorite[i] 是一条从 i 指向 favorite[i] 的有向边。因为每个点出度为 1，整个图由若干个“基环树”组成（即一个环，环上挂着若干树枝）。
2. 两种情况：
* 情况一（大环）：如果环的长度大于 2，那么只有环上的节点能坐在一起。树枝上的节点无法插入（因为会破坏环上节点的相邻关系）。
* 情况二（双向配对）：如果环的长度等于 2（即 A 喜欢 B，B 喜欢 A），那么 A 和 B 可以坐在一起。此时，挂在 A 和 B 身上的“树枝”可以延伸出来，形成 链 -> A B 2 的最大环长度。
* 遍历所有长度为 2 的环，累加 最长链A + 最长链B + 2。
* 返回最大值。
💻 Python3 代码实现
from collections import deque
from typing import List
class Solution:
def maximumInvitations(self, favorite: List[int]) -> int:
n = len(favorite)
# 1. 计算入度
indegree = [0] * n
for i in range(n):
indegree[favorite[i]] += 1
# 2. 拓扑排序（剪枝）
# 将所有入度为 0 的节点（树枝末端）加入队列
queue = deque()
for i in range(n):
if indegree[i] == 0:
queue.append(i)
# max_depth[i] 表示以 i 为终点的最长链长度（包含 i）
max_depth = [1] * n
while queue:
u = queue.popleft()
v = favorite[u] # u 指向 v
# 更新 v 的最长链长度：v 的深度 = max(v 当前深度, u 的深度 + 1)
max_depth[v] = max(max_depth[v], max_depth[u] + 1)
# 减少 v 的入度，如果 v 的入度变为 0，说明 v 也是树枝的一部分
indegree[v] -= 1
if indegree[v] == 0:
queue.append(v)
# 3. 处理环
max_cycle_size = 0 # 记录长度 > 2 的最大环
sum_pair_size = 0 # 记录所有长度为 2 的环及其链的总和
for i in range(n):
# 如果 indegree[i] == 0，说明 i 是树枝上的点，已经被处理过了
if indegree[i] == 0:
continue
# 找到一个环，计算环的大小
cycle_size = 0
cur = i
while indegree[cur] != 0: # 只要还在环里
indegree[cur] = 0 # 标记为已访问（置为0，避免重复计算）
cur = favorite[cur]
cycle_size += 1
if cycle_size == 2:
# 情况二：长度为 2 的环
# i 和 favorite[i] 互相喜欢
# 加上各自延伸出的最长链
sum_pair_size += max_depth[i] + max_depth[favorite[i]]
else:
# 情况一：长度 > 2 的环
max_cycle_size = max(max_cycle_size, cycle_size)
return max(max_cycle_size, sum_pair_size)
📝 关键点解析
1. 拓扑排序的作用：
* 它帮助我们剥离了所有的“树枝”，只留下环。
* 在剥离过程中，我们利用动态规划的思想（max_depth[v] = max(max_depth[v], max_depth[u] + 1)）计算出了每个环节点能延伸出的最长链长度。
2. 处理长度为 2 的环：
* 当 cycle_size == 2 时，这两个节点 u 和 v 互相喜欢。
* max_depth[u] 已经包含了 u 自己以及它身后最长链的长度。
* max_depth[v] 同理。
* 所以总长度就是 max_depth[u] + max_depth[v]。
3. 处理长度 > 2 的环：
* 这种环是封闭的，不能外挂任何节点，所以直接取最大的环长度即可。
📊 复杂度分析
* 时间复杂度：O(n)。拓扑排序遍历所有节点和边一次，找环的过程每个节点也只访问一次。
* 空间复杂度：O(n)。用于存储入度数组、队列和深度数组。