title
一个公司准备组织一场会议，邀请名单上有 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 无法参加，因为他喜欢的员工 0 旁边的座位已经被占领了。
所以公司只能不邀请员工 2 。
参加会议的最多员工数目为 4 。
提示：
n == favorite.length2 <= n <= 1050 <= favorite[i] <= n - 1favorite[i] != i
solution
o(n)
DFS 分析题目后，我们可以知道，有两种方式安排员工：
所有被安排的员工构成一个环：A->B->C->D->…->A 所有被安排的员工为若干个组，每个组的结构为：A->B->…->C↔D<-E<-…<-F 针对第一种情况，我们需要找出图中的最大环。在本题的限制之下（每个节点的出度都为1），不会出现环套环的情况，因此我们只需要枚举出所有的环即可。
针对第二种情况，我们需要在所有二元环的基础上，对于每一个二元环，在反向图中分别找出以其两个端点开始的最长链（注意排除二元环的另一方）。
在下面的参考代码中，对第一种情况的计算也是在反向图中进行的。
class Solution:
def maximumInvitations(self, favorite: List[int]) -> int:
regraph = collections.defaultdict(set)
n = len(favorite)
pairs = []
for i in range(len(favorite)):
regraph[favorite[i]].add(i)
if favorite[i] in regraph[i]:
pairs.append((i,favorite[i]))
color = [0] * n
depth = [0] * n
maxdepth = 0
# print(graph)
def dfs(u):
color[u] = 1
for v in regraph[u]:
if color[v] == 0:
depth[v] = depth[u] + 1
dfs(v)
elif color[v] == 1:
nonlocal maxdepth
maxdepth = max(maxdepth, depth[u] - depth[v] + 1)
color[u] = 2
for i in range(n):
if color[i] == 0:
dfs(i)
# print(depth)
# print(maxdepth)
def dfs2(u, p):
ans = 1
for v in regraph[u]:
if v == p: continue
ans = max(ans, dfs2(v, p) + 1)
return ans
from_pairs = 0
for u, v in pairs:
from_pairs += dfs2(u, v)
from_pairs += dfs2(v, u)
return max(from_pairs, maxdepth)