首页 > 试题广场 >

上司的舞会

[编程题]上司的舞会
  • 热度指数：142 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
\hspace{15pt}公司共有 n 名员工（编号 1\sim n）。每名员工要么没有直接上司（即为最高层，数据保证最高层唯一），要么恰有一名直接上司。若员工 A 是员工 B 的直接或间接上司（即直接上级的直接上级、直接上级的直接上级的直接上级、直接上级的直接上级的直接上级的直接上级......），则称 A 是 B 的上级。

\hspace{15pt}现在需要将所有员工分到若干舞会小组，满足：
{\hspace{23pt}}1. 每位员工恰好属于一个小组；
{\hspace{23pt}}2. 同一小组内不得出现任何一对员工具有上级关系。

\hspace{15pt}求满足要求的最小小组数量。

输入描述:
\hspace{15pt}第一行输入整数 n\left(1\leqq n\leqq 2000\right)。
\hspace{15pt}接下来一行输入 n 个整数 p_i，其中
{\hspace{23pt}}\bullet\,p_i=-1 表示第 i 号员工没有直接上司；
{\hspace{23pt}}\bullet\,p_i\neq -1 表示第 i 号员工的直接上司编号为 p_i。


输出描述:
\hspace{15pt}输出一个整数，表示最小所需小组数。
示例1

输入

5
-1 1 2 1 -1

输出

3
算法知识视频讲解
添加回答
饭吃了饿头像 饭吃了饿
最高层不是唯一么，为啥示例1里有2个-1？
发表于 2025-11-12 11:50:39 回复(0)
提交观点

问题信息

难度：
1条回答 30浏览

热门推荐

相关试题

上司的舞会

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号