题目描述
2023.11.1 每日一题
$2127.$参加会议的最多员工数
一个公司准备组织一场会议,邀请名单上有 $n$ 位员工。公司准备了一张圆形的桌子,可以坐下任意数目的员工。
员工编号为 $0$ 到 $n-1$。每位员工都有一位喜欢的员工,每位员工当且仅当他被安排在喜欢员工的旁边,他才会参加会议。每位员工喜欢的员工不会是他自己。
给你一个下标从 $0$ 开始的整数数组 $favorite$ ,其中 $favorite[i]$ 表示第 $i$ 位员工喜欢的员工。请你返回参加会议的最多员工数目 。
样例
输入
favorite = [2,2,1,2]
输出
3
基环内向树
时间复杂度:$O(n)$ 空间复杂度:$O(n)$
参考了LeetCode官方题解的思路,学习到了新的知识点[基环内向树]。
基环内向树,即n个点n条边的图,每个点的出度为1(若每点入度为1,则为基环外向树)。基环内向树可以利用拓扑排序找环。找环的目的可以到原链接参考官方题解,题解的解释和证明都给的很不错,此处不再赘述。
C++ 代码
class Solution {
public:
int maximumInvitations(vector<int>& favorite) {
int n=favorite.size();
vector<int> indeg(n,0);
queue<int> q;
vector<bool> vis(n,false);
vector<int> f(n,1);
for(int i=0;i<n;i++) indeg[favorite[i]]++;
for(int i=0;i<n;i++) if(!indeg[i]) q.push(i);
while(q.size()){
int u=q.front();q.pop();
vis[u]=true;
int v=favorite[u];
indeg[v]--;
f[v]=max(f[v],f[u]+1);
if(!indeg[v]) q.push(v);
}
int sum=0,mx=0;
for(int i=0;i<n;i++){
if(!vis[i]){
int u=favorite[i];
vis[i]=true,vis[u]=true;
if(favorite[u]==i){
sum+=(f[i]+f[u]);
}
else{
int circle=2;
while(favorite[u]!=i){
circle++;
u=favorite[u];
vis[u]=true;
}
mx=max(circle,mx);
}
}
}
return max(sum,mx);
}
};
附:官解详细注释版
class Solution {
public:
int maximumInvitations(vector<int>& favorite) {
int n = favorite.size();
// 统计入度,便于进行拓扑排序
vector<int> indeg(n,0);
for (int i = 0; i < n; i++) {
indeg[favorite[i]]++;
}
vector<int> used(n,0), f(n, 1);
queue<int> q;
for (int i = 0; i < n; i++) {
if (indeg[i]==0) {
q.push(i);//拓扑排序处理,先把入度为0的点入队
}
}
while (!q.empty()) {//拓扑排序
int u = q.front();
used[u] = 1;
q.pop();
int v = favorite[u];//找出u指向的那个节点
// 状态转移
f[v] = max(f[v], f[u] + 1);//f[v]记录的是走到v的最长的双向游走路径长度
indeg[v]--;//v的入度减一
if (!indeg[v]) {//入度为0入队
q.push(v);
}
}
// ring 表示最大的环的大小
// total 表示所有环大小为 2 的「基环内向树」上的最长的「双向游走」路径之和
int ring = 0, total = 0;
for (int i = 0; i < n; i++) {
if (used[i]==0) {//拓扑排序后依然入度不为0,即成环
int j = favorite[i];//找到环上的一点i,沿着i往下走
if (favorite[j] == i) {//此种情况下i,j互为favorite,说明成的是二元环
total += (f[i] + f[j]);//此时i,j所在的块可以围成一个符合条件且可以从某处断开的环,所有二元环可以拼接在一起形成更大的环,故total值相加
used[i] = used[j] = true;
}
// 否则环的大小至少为 3,我们需要找出环
else {
int u = i, cnt = 0;
while (true) {
cnt++;
u = favorite[u];//一直找,直到遍历这个环
used[u] = true;
if (u == i) break;
}
ring = max(ring, cnt);//所有三元及以上环中取最大的
}
}
}
return max(ring, total);//返回两种情况中最大的
}
};