一个公司准备组织一场会议,邀请名单上有 n 位员工。公司准备了一张 圆形 的桌子,可以坐下 任意数目 的员工。
员工编号为 0 到 n – 1 。每位员工都有一位 喜欢 的员工,每位员工 当且仅当 他被安排在喜欢员工的旁边,他才会参加会议。每位员工喜欢的员工 不会 是他自己。
给你一个下标从 0 开始的整数数组 favorite ,其中 favorite[i] 表示第 i 位员工喜欢的员工。请你返回参加会议的 最多员工数目 。
示例 1:
输入:favorite = [2,2,1,2]
输出:3
解释:
上图展示了公司邀请员工 0,1 和 2 参加会议以及他们在圆桌上的座位。
没办法邀请所有员工参与会议,因为员工 2 没办法同时坐在 0,1 和 3 员工的旁边。
注意,公司也可以邀请员工 1,2 和 3 参加会议。
所以最多参加会议的员工数目为 3 。
示例 2:
输入:favorite = [1,2,0]
输出:3
解释:
每个员工都至少是另一个员工喜欢的员工。所以公司邀请他们所有人参加会议的前提是所有人都参加了会议。
座位安排同图 1 所示:
– 员工 0 坐在员工 2 和 1 之间。
– 员工 1 坐在员工 0 和 2 之间。
– 员工 2 坐在员工 1 和 0 之间。
参与会议的最多员工数目为 3 。
示例 3:
输入:favorite = [3,0,1,4,1]
输出:4
解释:
上图展示了公司可以邀请员工 0,1,3 和 4 参加会议以及他们在圆桌上的座位。
员工 2 无法参加,因为他喜欢的员工 0 旁边的座位已经被占领了。
所以公司只能不邀请员工 2 。
参加会议的最多员工数目为 4 。
提示:
n == favorite.length
2 <= n <= 105
0 <= favorite[i] <= n – 1
favorite[i] != i
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/maximum-employees-to-be-invited-to-a-meeting
解法:
根据大佬的题解,才知道本题是基环数问题:从i向favorite[i]连边,我们可以得到一张有向图。由于每个大小为k的连通块都有k个点和k条边,所以每个连通快必定有且仅有一个环,且由于每个点的出度均为1,这样的有向图又叫做内向基环树,由基环树组成的森林叫基环树森林。
每一个内向基环树(连通块)都由一个基环和其余指向基环的树枝组成。如下图一:0,1,2,3,4组成一棵基环树。
特别的,我们得到的基环可能只包含两个节点。如下图二:
在本题中,这两种情况有明显区别。
一:在本题中基环大小大于2的情况中,环最大的就是答案。二:基环大小等于2的情况,那么需要去计算每个基环树所对应的链。
在周赛时,通过自己画图,也想到了答案的形式,分为两类。但有两点没考虑到,第一:有多个图二这样的环,然后这些环之间用的是相加,而我用的是取最大值。第二: 我忘了用拓扑排序进行剪枝,导致我后续求环的大小极其麻烦。直到周赛结束才做出来,如下是我的原始代码。
class Solution {
int dfs(const vector<vector<int>> &gra, int x, vector<bool> &vis)
{
//if (gra[x].size()==0) return 1;
int cnt = 0;
for (auto u : gra[x])
{
if (!vis[u])
{
vis[u] = true;
cnt = max(cnt, dfs(gra, u, vis));
}
}
return cnt+1;
}
public:
int maximumInvitations(vector<int>& favorite) {
int n = favorite.size();
if (n <= 3)
return n;
vector<int> temp; //记录 环内只有两个元素的环
vector<int> ind(n), outd(n); //入度,出度
vector<vector<int>> gra(n); //反向图,用于计算链的长度
for (int i = 0; i < n; ++i)
{
int v = favorite[i];
if (favorite[v] == i&&v>i)
temp.push_back(i);
++ind[v];
++outd[i];
gra[v].push_back(i);
}
vector<bool> vis(n);
int ans = 0;
for (auto &t : temp) //先处理环内只有两个点的情况。
{
int cnt = 0;
vis[t] = true;
vis[favorite[t]] = true;
cnt+=dfs(gra, t, vis); //第一个点的最长链的长度
cnt += dfs(gra, favorite[t], vis); //第二个点的最长链的长度
ans += cnt; //不同环之间用相加
}
for (int i = 0; i < n; ++i)
{
if (!vis[i] && ind[i] >= outd[i])
{
int cnt = 0;
int u = i;
while (!vis[u])
{
vis[u] = true;
++cnt;
u = favorite[u];
}
if (u==i) //起点等于终点,那么i就是在环内
ans = max(ans, cnt);
else //不然,u可能是环内
{
cnt = 0;
//int t = favorite[u];
vector<bool> v(n); //防止链的所属环已经被计算过了。
int t = u;
while (!v[t])
{
v[t] = true;
++cnt;
t = favorite[t];
}
if (u==t)
ans = max(ans, cnt);
}
}
}
return ans;
}
};
看了大佬的题解后,重新编写了代码:
class Solution {
int dfs(const vector<vector<int>> &gra, int x, vector<bool> &vis)
{
//if (gra[x].size()==0) return 1;
int cnt = 0;
for (auto u : gra[x])
{
if (!vis[u])
{
vis[u] = true;;
cnt = max(cnt, dfs(gra, u, vis));
}
}
return cnt+1;
}
public:
int maximumInvitations(vector<int>& favorite) {
int n = favorite.size();
if (n <= 3)
return n;
vector<int> ind(n); //入度
vector<vector<int>> gra(n); //反向图
for (int i = 0; i < n; ++i)
{
int v = favorite[i];
++ind[v];
gra[v].push_back(i);
}
vector<bool> vis(n);
int ans1 = 0, ans2=0;
queue<int> q;
for (int i = 0; i < n; ++i)
{
if (ind[i] == 0)q.push(i);
}
while (!q.empty())
{
int u = q.front();
q.pop();
int v = favorite[u];
--ind[v];
if (ind[v]==0)
q.push(v);
}
auto getCnt = [&](int x){
int cnt = 0;
while (!vis[x])
{
++cnt;
vis[x] = true;
x = favorite[x];
}
return cnt;
};
for (int i = 0; i < n; ++i)
{
if (!vis[i]&&ind[i] >0)
{
int cnt = getCnt(i);
if (cnt == 2)
{
vis[i] = true, vis[favorite[i]] = true;
ans1+=dfs(gra, i, vis) + dfs(gra, favorite[i], vis);
}
else
{
ans2 = max(ans2, cnt);
}
}
}
return max(ans1, ans2);
}
};
文章出处登录后可见!