LeetCode 题解工作台
参加会议的最多员工数
一个公司准备组织一场会议，邀请名单上有 n 位员工。公司准备了一张 圆形 的桌子，可以坐下 任意数目 的员工。 员工编号为 0 到 n - 1 。每位员工都有一位 喜欢 的员工，每位员工 当且仅当 他被安排在喜欢员工的旁边，他才会参加会议。每位员工喜欢的员工 不会 是他自己。 给你一个下标从 0 开…
3
题型
5
代码语言
3
相关题
当前训练重点
困难 · 图·搜索
答案摘要
我们观察发现，题目中员工的喜好关系可以看作一个有向图，这个有向图可以分成多个“基环内向树”的结构。在每个结构中，包含一个环，而环上的每个节点都连接着一棵树。 什么是“基环内向树”？首先，基环树是一个具有 个节点 条边的有向图，而内向树是指这个有向图中，每个节点都有且仅有一条出边。本题中，每个员工都有且仅有一个喜欢的员工，因此，构成的有向图可以由多个“基环内向树”构成。
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 图·搜索 题型思路
题目描述
一个公司准备组织一场会议，邀请名单上有 n 位员工。公司准备了一张 圆形 的桌子，可以坐下 任意数目 的员工。
员工编号为 0 到 n - 1 。每位员工都有一位 喜欢 的员工，每位员工 当且仅当 他被安排在喜欢员工的旁边，他才会参加会议。每位员工喜欢的员工 不会 是他自己。
给你一个下标从 0 开始的整数数组 favorite ，其中 favorite[i] 表示第 i 位员工喜欢的员工。请你返回参加会议的 最多员工数目 。
示例 1：
输入：favorite = [2,2,1,2] 输出：3 解释： 上图展示了公司邀请员工 0，1 和 2 参加会议以及他们在圆桌上的座位。 没办法邀请所有员工参与会议，因为员工 2 没办法同时坐在 0，1 和 3 员工的旁边。 注意，公司也可以邀请员工 1，2 和 3 参加会议。 所以最多参加会议的员工数目为 3 。
示例 2：
输入：favorite = [1,2,0] 输出：3 解释： 每个员工都至少是另一个员工喜欢的员工。所以公司邀请他们所有人参加会议的前提是所有人都参加了会议。 座位安排同图 1 所示： - 员工 0 坐在员工 2 和 1 之间。 - 员工 1 坐在员工 0 和 2 之间。 - 员工 2 坐在员工 1 和 0 之间。 参与会议的最多员工数目为 3 。
示例 3：
输入：favorite = [3,0,1,4,1] 输出：4 解释： 上图展示了公司可以邀请员工 0，1，3 和 4 参加会议以及他们在圆桌上的座位。 员工 2 无法参加，因为他喜欢的员工 1 旁边的座位已经被占领了。 所以公司只能不邀请员工 2 。 参加会议的最多员工数目为 4 。
提示：
n == favorite.length2 <= n <= 1050 <= favorite[i] <= n - 1favorite[i] != i
解题思路
方法一：图的最大环 + 最长链
我们观察发现，题目中员工的喜好关系可以看作一个有向图，这个有向图可以分成多个“基环内向树”的结构。在每个结构中，包含一个环，而环上的每个节点都连接着一棵树。
什么是“基环内向树”？首先，基环树是一个具有 个节点 条边的有向图，而内向树是指这个有向图中，每个节点都有且仅有一条出边。本题中，每个员工都有且仅有一个喜欢的员工，因此，构成的有向图可以由多个“基环内向树”构成。
对于本题，我们可以求出图的最大环的长度，这里我们只需要求出最大的一个环的长度，这是因为，如果有多个环，那么不同环之间是不连通的，不符合题意。
另外，对于环的大小等于 的长度，即存在两个员工互相喜欢，那么我们可以把这两个员工安排在一起，如果这两个员工各自被别的员工喜欢，那么我们只需要把喜欢他们的员工安排在他们的旁边即可。如果有多个这样的情况，我们可以把他们都安排上。
因此，问题实际上等价于求出图的最大环的长度，以及所有长度为 的环加上其最长链。求这两者的最大值即可。求最长链到长度为 的环，我们可以使用拓扑排序。
时间复杂度 ，空间复杂度 。其中 为数组 favorite 的长度。
相似题目：
class Solution:
def maximumInvitations(self, favorite: List[int]) -> int:
def max_cycle(fa: List[int]) -> int:
n = len(fa)
vis = [False] * n
ans = 0
for i in range(n):
if vis[i]:
continue
cycle = []
j = i
while not vis[j]:
cycle.append(j)
vis[j] = True
j = fa[j]
for k, v in enumerate(cycle):
if v == j:
ans = max(ans, len(cycle) - k)
break
return ans
def topological_sort(fa: List[int]) -> int:
n = len(fa)
indeg = [0] * n
dist = [1] * n
for v in fa:
indeg[v] += 1
q = deque(i for i, v in enumerate(indeg) if v == 0)
while q:
i = q.popleft()
dist[fa[i]] = max(dist[fa[i]], dist[i] + 1)
indeg[fa[i]] -= 1
if indeg[fa[i]] == 0:
q.append(fa[i])
return sum(dist[i] for i, v in enumerate(fa) if i == fa[fa[i]])
return max(max_cycle(favorite), topological_sort(favorite))
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | complexity is O(n) because each node is visited once in DFS and during topological sorting. Space complexity is O(n) to store graph edges, indegree counts, and visited status for each employee. |
| 空间 | O(n) |
面试官常问的追问
外企场景- question_mark
The problem hints at using graph representation of the favorite array and tracking indegrees.
- question_mark
Interviewers expect recognition of cycles versus chains for seating calculations.
- question_mark
Applying DFS to compute longest chains before combining with cycles demonstrates mastery of topological order in graphs.
常见陷阱
外企场景- error
Ignoring chain contributions into two-employee mutual favorite cycles, which undercounts the maximum attendees.
- error
Misidentifying cycles due to revisiting nodes without proper visited tracking in DFS.
- error
Summing cycle lengths incorrectly, especially when combining chain-augmented two-node cycles with longer independent cycles.
进阶变体
外企场景- arrow_right_alt
Find the minimum number of employees to remove so that no favorite adjacency constraint is violated.
- arrow_right_alt
Determine the maximum number of employees that can be seated for multiple simultaneous round tables using the same favorite array.
- arrow_right_alt
Adapt the problem to allow employees to attend if seated next to anyone within two positions of their favorite.