一、题目
1、题目描述2、基础框架3、原题链接 二、解题报告
1、思路分析2、时间复杂度3、代码详解 三、本题小知识四、加群须知
一、题目 1、题目描述2、基础框架一个公司准备组织一场会议，邀请名单上有 n n n 位员工。公司准备了一张圆形的桌子，可以坐下任意数目的员工。员工编号为 0 0 0 到 n − 1 n - 1 n−1 。每位员工都有一位喜欢的员工，每位员工当且仅当他被安排在喜欢员工的旁边，他才会参加会议。每位员工喜欢的员工不会是他自己。给你一个下标从0 开始的整数数组 favorite，其中 favorite[i]表示第 i i i 位员工喜欢的员工。请你返回参加会议的最多员工数目。
样例输入： favorite = [2,2,1,2]
样例输出： 3
C语言 版本给出的基础框架代码如下：
int maximumInvitations(int* favorite, int favoriteSize){
}
3、原题链接
二、解题报告 1、思路分析LeetCode 2127. 参加会议的最多员工数
(
1
)
(1)
(1) 首先问几个问题：是不是一定有环？有没有可能有多个环？如果有多个环，这多个环的人能不能都加上会议？
(
2
)
(2)
(2) 是不是一定有环？答案是一定有。假设没有环，对于某一条链的末尾结点，指向的一定是链外的结点，这样它就不可能是末尾结点，和假设矛盾。所以它一定指向链内的结点，这样就形成了环。
(
3
)
(3)
(3) 有没有可能有多个环？有可能。
(
4
)
(4)
(4) 如果有多个两人以上环，这多个环的人能不能都加上会议？答案是不行，因为参加会议的一定是一个连通图。如果把两个环的人弄进来，就一定不可能是一个连通图了。
(
4.1
)
(4.1)
(4.1) 所有入度为零的结点，对整个环不产生贡献；
(
4.2
)
(4.2)
(4.2) 去掉所有入度为零的结点，并且将它指向的结点入度减一，如果那个结点变成了入度为零的点，那么，它对这个环也是没有贡献的。
(
4.3
)
(4.3)
(4.3) 按照这样的方法，把所有没有贡献的结点去掉，这就是 拓扑排序，可以利用广度优先搜索来实现。
(
5
)
(5)
(5) 如果有一个二人环，那么分别从两个人去找各自的 “被喜欢人” 的最长链 加和以后就是一个可行解。
(
5.1
)
(5.1)
(5.1) 对于这种情况，我们可以分别对两个互相喜欢的结点进行向外找最长路（注意，这里要建反向边），对于这两个结点，其实分别是一棵树。于是，问题转变成了求树的从根结点到叶子结点的最长路。
(
5.2
)
(5.2)
(5.2) 任意的两两喜欢的链，都一定可以放进圆桌会议。
O ( n ) O(n) O(n)。
3、代码详解class Solution {
vector edges[100010];
queue q;
bool visited[100010];
int inDegree[100010];
int maxlink(int u, int ban) {
int i;
int maxl = 1;
for(i = 0; i < edges[u].size(); ++i) {
int v = edges[u][i];
if(v == ban) {
continue;
}
maxl = max(maxl, maxlink(v, ban) + 1);
}
return maxl;
}
void init(int n, vector& favorite) {
memset(inDegree, 0, sizeof(inDegree));
memset(visited, 0, sizeof(visited));
while(!q.empty()) q.pop();
for(int i = 0; i < n; ++i) {
edges[i].clear();
}
for(int i = 0; i < n; ++i) {
// a -> b 表示 a 喜欢 b
int a = i;
int b = favorite[i];
++inDegree[b]; // 建立入度表
edges[b].push_back(a); // 建立反向图
}
}
public:
int maximumInvitations(vector& favorite) {
int i;
int ans = 0, x;
int n = favorite.size();
init(n, favorite);
// a 和 b 互相喜欢，并且 a 找最长路， b 找最长路，然后相加
for(i = 0; i < n; ++i) {
int a = i;
int b = favorite[i];
if(favorite[b] == a) { // 说明 a 和 b 互相喜欢
x = maxlink(a, b) + maxlink(b, a);
ans = ans + x;
}
}
ans /= 2;
for(i = 0; i < n; ++i) {
if(!inDegree[i]) {
q.push(i);
visited[i] = 1;
}
}
// 拓扑排序
// 因为舔狗不得house，所以我们需要给他一个家，这个家就是我们的队列
// 于是，最后所有visited[i] = 1对应的i，都是舔狗
while(!q.empty()) {
int u = q.front();
q.pop();
int v = favorite[u];
if(--inDegree[v] == 0) {
q.push(v);
visited[v] = 1;
}
}
for(i = 0; i < n; ++i) {
if(visited[i]) {
continue;
}
visited[i] = 1;
int cnt = 1;
int start = favorite[i];
while(start != i) {
visited[start] = 1;
++cnt;
start = favorite[start];
}
ans = max(ans, cnt);
}
return ans;
}
};
三、本题小知识
遇到图的问题，要根据图的特殊性（比如这道题的图，每个结点一定有一条出边）来思考对应的解题方案，而不是盲目的去找环。
四、加群须知
相信看我文章的大多数都是「 大学生 」，能上大学的都是「 精英 」，那么我们自然要「 精益求精 」，如果你还是「 大一 」，那么太好了，你拥有大把时间，当然你可以选择「 刷剧 」，然而，「 学好算法 」，三年后的你自然「 不能同日而语 」。
那么这里，我整理了「 几十个基础算法 」 的分类，点击开启：
如果链接被屏蔽，或者有权限问题，可以私聊作者解决。
大致题集一览：
为了让这件事情变得有趣，以及「 照顾初学者 」，目前题目只开放最简单的算法 「 枚举系列 」 （包括：线性枚举、双指针、前缀和、二分枚举、三分枚举），当有 一半成员刷完 「 枚举系列 」 的所有题以后，会开放下个章节，等这套题全部刷完，你还在群里，那么你就会成为「 夜深人静写算法 」专家团 的一员。
不要小看这个专家团，三年之后，你将会是别人 望尘莫及 的存在。如果要加入，可以联系我，考虑到大家都是学生， 没有「 主要经济来源 」，在你成为神的路上，「 不会索取任何 」。
联系作者，或者扫作者主页二维码加群，加入刷题行列吧
让天下没有难学的算法
C语言免费动漫教程，和我一起打卡！ 《光天化日学C语言》
让你养成九天持续刷题的习惯 《九日集训》
入门级C语言真题汇总 李《C语言入门100例》李
组团学习，抱团生长 《算法零基础100讲》
几张动图学会一种数据结构 《画解数据结构》
竞赛选手金典图文教程 《夜深人静写算法》
