题目
https://leetcode.cn/problems/maximum-employees-to-be-invited-to-a-meeting/description/
题解
从 \(i\) 向 \(favorite[i]\) 连边，会形成一张 \(n\) 个点 \(n\) 条边的有向图，且该图包含若干个连通块，每个连通块均为基环树，亦即该有向图为基环树森林。
以测试用例[1, 2, 0]，进行分析：
假设从中选择任意的点，例如：
此时显然没有全部人喜欢的人都参加会议，由于 \(1\) 喜欢的人未参加，故而该选法必定不会满足。那么什么情况可以满足每个人喜欢的人都有参加呢？
答：存在一个环的时候，可以使得每个人喜欢的人都有参加。
由于参加会议是坐在圆桌上，因此隐含了一个条件：每个人周围至多可以坐两个不同的人，但其中一个必须是喜欢之人。
若参加会议的人，全部位于环上，明显全部可以参加。
若参加会议的人，不止环上的人，则需要进行以下分类讨论：
- 环上人数大于 \(2\)：环上的每个人，两侧必定是一个为自己喜欢之人，一个为喜欢自己之人，因此周围两个人都是确定的，若还有位于环外的人喜欢自身，会造成坐在自身旁边的人数超过 \(2\)，会破坏周围只能做两个不同的人的条件。因此，该种情况环的大小就是答案；
- 环上人数等于 \(2\)：环上的人，坐在一起后，周围均可以再坐一个喜欢自己之人。因此，该种情况就是环的大小加两个不同节点的最大外链长度。且该种情况，可以多个环进行累计，因为每个环的外链末端都可以再坐一个人。
参考代码
class Solution {
public:
int maximumInvitations(vector<int>& favorite) {
int ans = 0, n = favorite.size(), cnt = 0;
vector<int> in(n), mx(n), v;
for (int &f: favorite) ++ in[f];
for (int i = 0; i < n; ++ i) if (!in[i]) v.emplace_back(i);
for (int fr = 0, rr = v.size(); fr < rr; rr = v.size()) {
while (fr < rr) {
int &cur = v[fr], &nxt = favorite[v[fr]];
mx[nxt] = max(mx[nxt], mx[cur] + 1);
if (-- in[nxt] == 0) v.emplace_back(nxt);
++ fr;
}
}
for (int i = 0; i < n; ++ i) {
if (in[i]) {
int res = 0, m1 = 0, m2 = 0;
for (int j = i; in[j] > 0; j = favorite[j]) {
-- in[j];
if (m1 < mx[j]) m2 = m1, m1 = mx[j];
else if (m2 < mx[j]) m2 = mx[j];
++ res;
}
if (res == 2) cnt += res + m1 + m2;
else ans = max(ans, res);
}
}
ans = max(ans, cnt);
return ans;
}
};