题目
题目来源: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); }
}
|