题目
题目来源：2127. 参加会议的最多员工数（每日一题）
一个公司准备组织一场会议，邀请名单上有 n 位员工。公司准备了一张 圆形 的桌子，可以坐下 任意数目 的员工。
员工编号为 0 到 n - 1 。每位员工都有一位 喜欢 的员工，每位员工 当且仅当 他被安排在喜欢员工的旁边，他才会参加会议。每位员工喜欢的员工 不会 是他自己。
给你一个下标从 0 开始的整数数组 favorite ，其中 favorite[i] 表示第 i 位员工喜欢的员工。请你返回参加会议的 最多员工数目 。
示例 1
输入：favorite = [2,2,1,2]
输出：3
示例 2
输入：favorite = [1,2,0]
输出：3
示例 3
输入：favorite = [3,0,1,4,1]
输出：4
思路
根据 favorite 的定义，如果将每个员工视作一个节点，指向自己喜欢的员工，那么 $n$ 条边、$n$ 个节点、每个节点的出度为 $1$ ，这形成了一个有向有环图。
观察示例 2 和 示例 3，参加圆桌会议的员工一定形成一个环。因为每个节点的出度为 $1$，该员工又必须坐在自己喜欢的员工旁。所以，参加会议的最多员工数目，等于最大环的长度。（结论 1️⃣）
结论 1️⃣也可以反过来论证：
观察示例 3，节点 2 不能参加会议，因为将该员工插入圆桌任一位置后不符合条件——已有的环被打破了。例如，将 2 插入 0 和 1 之间，那么 1 的旁边是 2 和 4，都不是自己喜欢的员工，条件不再成立。
所以，那些能参加会议的员工组成的图，一定是一个环，不可能再有其他节点链（单向链表）指向环中的某个节点。
如图，答案是 $\set{0,1,2,3}$，而不可能包含 $\set{7,8}$ 和 $\set{4,5,6}$。
但是，对于长度为 2 的环（互相指向的两个节点），只要两个员工坐在一起，这个环就无法被打破。因此，长度为 2 的环需要特殊处理。观察示例 1，节点 1 和 2 形成环，此时的圆桌可以再进入 1 人。
再观察如下示例：
节点 0 和 1 形成长度为 2 的环，节点链 $(3,2)$ 指向 0，节点链$(5,4),(6)$ 指向 1。最终圆桌上的员工按顺序依次为：$3,2,0,1,4,5$。即以环为中心，选择环中两个节点各自最长的节点链加入结果集。（结论2️⃣）所以，我们选择 $(5,4)$，而不是 $(6)$。
注意到，这个图可能包含多个连通分量。我们需要修正上述两个结论：
- 对于长度大于 2 的环，整个圆桌必须归其中的节点所有，不允许其它节点出现。因此，当有多个环时，选择长度最大的作为结果。
- 对于长度等于 2 的环，“每位员工当且仅当他被安排在喜欢员工的旁边，他才会参加会议”，这个条件的成立仅仅依赖于环，而不依赖于独占圆桌。因此，最终的结果是符合『结论2️⃣』的所有结果集的并集。一个结果集中的员工只要坐在一起，那么所有的结果集就能同时存在。
观察下面的示例，答案为三个长度为 2 的环和延伸出去的节点链，总共 8 个节点；而剩下的连通分量，是一个长度为 4 的环。
代码
根据上一节的推论，我们在代码中需要求得如下信息：
- 各个环的长度
- 长度为 2 的环的每个节点的节点链的最大长度
如何找到图中的环？
拓扑排序。因为这是包含 $n$ 条边、$n$ 个节点、每个节点的出度为 $1$ 的有向图，因此拓扑排序过程中无法被访问的节点一定是环中的节点。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
| int n = favorite.length;
int[] inDegree = new int[n];
ArrayDeque<Integer> que = new ArrayDeque<>();
boolean[] visited = new boolean[n];
for (int i = 0; i < n; i++) {
inDegree[favorite[i]]++;
}
for (int i = 0; i < n; i++) {
if (inDegree[i] == 0) {
que.add(i);
}
}
while (!que.isEmpty()) {
int cur = que.pollFirst();
visited[cur] = true;
int next = favorite[cur];
inDegree[next]--;
if (inDegree[next] == 0) {
que.addLast(next);
}
}
int maxCircleSize = 0;
for (int i = 0; i < n; i++) {
if (visited[i]) continue;
ArrayList<Integer> circle = new ArrayList<>();
int cur = i;
while (!visited[cur]) {
circle.add(cur);
visited[cur] = true;
cur = favorite[cur];
}
maxCircleSize = Math.max(maxCircleSize, circle.size());
}
|
如何统计节点链？
节点链是不属于环的单链表。该链表从一个入度为 0 的节点开始，以指向一个环中节点而结束。我们可以定义一个 pathLen 数组，pathLen[i] 表示指向节点 i 的最长节点链的长度
由于拓扑排序不断地遍历当前入度为 0 的节点，如果节点 a 指向 b，那么 a 一定先被访问。如果 a 的节点链已经计算完毕，那么我们可以很方便地计算 b 的节点链：
$pathLen[b] = \max\limits_{(a,b)\in E}\set{1 + pathLen[a]}$
所以我们可以在拓扑排序的过程中计算 pathLen：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
|
int[] pathLen = new int[n];
while (!que.isEmpty()) {
int cur = que.pollFirst();
visited[cur] = true;
int next = favorite[cur];
pathLen[next] = Math.max(pathLen[next], pathLen[cur] + 1);
inDegree[next]--;
if (inDegree[next] == 0) {
que.addLast(next);
}
}
|
最终代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
| import java.util.ArrayDeque;
import java.util.ArrayList;
class Solution {
public int maximumInvitations(int[] favorite) {
int n = favorite.length;
int[] inDegree = new int[n];
int[] pathLen = new int[n];
ArrayDeque<Integer> que = new ArrayDeque<>();
boolean[] visited = new boolean[n];
for (int i = 0; i < n; i++) {
inDegree[favorite[i]]++;
}
for (int i = 0; i < n; i++) {
if (inDegree[i] == 0) {
que.add(i);
}
}
while (!que.isEmpty()) {
int cur = que.pollFirst();
visited[cur] = true;
int next = favorite[cur];
pathLen[next] = Math.max(pathLen[next], pathLen[cur] + 1);
inDegree[next]--;
if (inDegree[next] == 0) {
que.addLast(next);
}
}
int maxCircleLength = 0;
int twoCirclePath = 0;
for (int i = 0; i < n; i++) {
if (visited[i]) continue;
ArrayList<Integer> circle = new ArrayList<>();
int cur = i;
while (!visited[cur]) {
circle.add(cur);
visited[cur] = true;
cur = favorite[cur];
}
maxCircleLength = Math.max(maxCircleLength, circle.size());
if (circle.size() == 2) {
twoCirclePath += pathLen[circle.get(0)] + pathLen[circle.get(1)] + 2;
}
}
return Math.max(maxCircleLength, twoCirclePath);
}
}
|