10395: 参加会议的最多员工数
[Creator : ]
Description
一个公司准备组织一场会议,邀请名单上有 $n$ 位员工。公司准备了一张圆形的桌子,可以坐下任意数目的员工。
员工编号为 $0$ 到 $n-1$。每位员工都有一位喜欢的员工,每位员工当且仅当他被安排在喜欢员工的旁边,他才会参加会议。每位员工喜欢的员工不会是他自己。
给你一个下标从 0 开始的整数数组 favorite,其中 favorite[i] 表示第 $i$ 位员工喜欢的员工。请你返回参加会议的最多员工数目。
员工编号为 $0$ 到 $n-1$。每位员工都有一位喜欢的员工,每位员工当且仅当他被安排在喜欢员工的旁边,他才会参加会议。每位员工喜欢的员工不会是他自己。
给你一个下标从 0 开始的整数数组 favorite,其中 favorite[i] 表示第 $i$ 位员工喜欢的员工。请你返回参加会议的最多员工数目。
Input
第一行包括两个整数 $n\ (2\leq n \leq 5\times 10^5)$。
第二行 $n$ 个整数,第 $i$ 个表示 favorite[i]。
第二行 $n$ 个整数,第 $i$ 个表示 favorite[i]。
Output
一个整数,参加会议的最多员工数目。
Sample 1 Input
4
2 2 1 2
Sample 1 Output
3
上图展示了公司邀请员工 0,1 和 2 参加会议以及他们在圆桌上的座位。
没办法邀请所有员工参与会议,因为员工 2 没办法同时坐在 0,1 和 3 员工的旁边。
注意,公司也可以邀请员工 1,2 和 3 参加会议。 所以最多参加会议的员工数目为 3。
Sample 2 Input
5
3 0 1 4 1
Sample 2 Output
4
上图展示了公司可以邀请员工 0,1,3 和 4 参加会议以及他们在圆桌上的座位。 员工 2 无法参加,因为他喜欢的员工 1 旁边的座位已经被占领了。 所以公司只能不邀请员工 2 。 参加会议的最多员工数目为 4 。
Sample 3 Input
3
1 2 0
Sample 3 Output
3
每个员工都至少是另一个员工喜欢的员工。所以公司邀请他们所有人参加会议的前提是所有人都参加了会议。
座位安排同图 1 所示:
- 员工 0 坐在员工 2 和 1 之间。
- 员工 1 坐在员工 0 和 2 之间。
- 员工 2 坐在员工 1 和 0 之间。
参与会议的最多员工数目为 3 。
- 员工 0 坐在员工 2 和 1 之间。
- 员工 1 坐在员工 0 和 2 之间。
- 员工 2 坐在员工 1 和 0 之间。
参与会议的最多员工数目为 3 。