codeforces --- 115A

时间:2021-10-31 20:50:33
A. Party
time limit per test

3 seconds

memory limit per test

256 megabytes

input

standard input

output

standard output

A company has n employees numbered from 1 to n. Each employee either has no immediate manager or exactly one immediate manager, who is another employee with a different number. An employee A is said to be the superior of another employee B if at least one of the following is true:

  • Employee A is the immediate manager of employee B
  • Employee B has an immediate manager employee C such that employee A is the superior of employee C.

The company will not have a managerial cycle. That is, there will not exist an employee who is the superior of his/her own immediate manager.

Today the company is going to arrange a party. This involves dividing all n employees into several groups: every employee must belong to exactly one group. Furthermore, within any single group, there must not be two employees A and B such that A is the superior of B.

What is the minimum number of groups that must be formed?

Input

The first line contains integer n (1 ≤ n ≤ 2000) — the number of employees.

The next n lines contain the integers pi (1 ≤ pi ≤ n or pi = -1). Every pi denotes the immediate manager for the i-th employee. If pi is -1, that means that the i-th employee does not have an immediate manager.

It is guaranteed, that no employee will be the immediate manager of him/herself (pi ≠ i). Also, there will be no managerial cycles.

Output

Print a single integer denoting the minimum number of groups that will be formed in the party.

Sample test(s)
input
5
-1
1
2
1
-1
output
3

思路:求树的高度。用并查集,不要压缩路径。

 #include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int father[], cnt;
int max(int x, int y)
{
return x > y ? x : y;
}
void init(int n)
{
for(int i = ;i <= n;i ++)
father[i] = i;
} void find(int x)
{
if(x == father[x])
return;
cnt ++;
find(father[x]);
} void unit(int x, int y)
{
father[x] = y;
return ;
} int main(int argc, char const *argv[])
{
int n, ans, temp;
while(~scanf("%d", &n))
{
init(n);
for(int i = ;i <= n;i ++)
{
scanf("%d", &temp);
if(temp != -)
unit(i, temp);
}
ans = ;
for(int i = ;i <= n;i ++)
{
cnt = ;
find(i);
ans = max(ans, cnt);
}
printf("%d\n", ans+);
}
return ;
}

codeforces --- 115A的更多相关文章

  1. python爬虫学习&lpar;5&rpar; —— 扒一下codeforces题面

    上一次我们拿学校的URP做了个小小的demo.... 其实我们还可以把每个学生的证件照爬下来做成一个证件照校花校草评比 另外也可以写一个物理实验自动选课... 但是出于多种原因,,还是绕开这些敏感话题 ...

  2. 【Codeforces 738D】Sea Battle(贪心)

    http://codeforces.com/contest/738/problem/D Galya is playing one-dimensional Sea Battle on a 1 × n g ...

  3. 【Codeforces 738C】Road to Cinema

    http://codeforces.com/contest/738/problem/C Vasya is currently at a car rental service, and he wants ...

  4. 【Codeforces 738A】Interview with Oleg

    http://codeforces.com/contest/738/problem/A Polycarp has interviewed Oleg and has written the interv ...

  5. CodeForces - 662A Gambling Nim

    http://codeforces.com/problemset/problem/662/A 题目大意: 给定n(n <= 500000)张卡片,每张卡片的两个面都写有数字,每个面都有0.5的概 ...

  6. CodeForces - 274B Zero Tree

    http://codeforces.com/problemset/problem/274/B 题目大意: 给定你一颗树,每个点上有权值. 现在你每次取出这颗树的一颗子树(即点集和边集均是原图的子集的连 ...

  7. CodeForces - 261B Maxim and Restaurant

    http://codeforces.com/problemset/problem/261/B 题目大意:给定n个数a1-an(n<=50,ai<=50),随机打乱后,记Si=a1+a2+a ...

  8. CodeForces - 696B Puzzles

    http://codeforces.com/problemset/problem/696/B 题目大意: 这是一颗有n个点的树,你从根开始游走,每当你第一次到达一个点时,把这个点的权记为(你已经到过不 ...

  9. CodeForces - 148D Bag of mice

    http://codeforces.com/problemset/problem/148/D 题目大意: 原来袋子里有w只白鼠和b只黑鼠 龙和王妃轮流从袋子里抓老鼠.谁先抓到白色老鼠谁就赢. 王妃每次 ...

随机推荐

  1. pandas 学习(1): pandas 数据结构之Series

    1. Series Series 是一个类数组的数据结构,同时带有标签(lable)或者说索引(index). 1.1 下边生成一个最简单的Series对象,因为没有给Series指定索引,所以此时会 ...

  2. 重置按钮小tip—为何不能重置表单数据呢

    刚开始学html的同志有时候可能会遇到一个问题,就是为什么在编辑页面里面的重置按钮总是不起作用呢不清空数据呢?接下来就说明一下原因. Reset 对象 Reset 对象代表 HTML 表单中的一个重置 ...

  3. JAVA 实现FTP上传下载&lpar;sun&period;net&period;ftp&period;FtpClient&rpar;

    package com.why.ftp; import java.io.DataInputStream; import java.io.File; import java.io.FileInputSt ...

  4. 用Android Studio 出现的问题

    解决的办法是cmd--恢复网络设置---netsh winsock reset----重启电脑解决.

  5. ajax 异步加载显示等待效果

    css: #loading { width:170px; height:25px; border:3px solid #C3DAF9; position:absolute; top:300px; le ...

  6. arcgis破解的时候,不能启动license manager的问题

    1.防火墙没关:(非常重要) 2.win+R,调出控制台,输入services.msc.然后手动开启ArcGIS license manager服务,关闭其余类似erdas,matlab影响该服务的开 ...

  7. CANopen--基于DS402协议的伺服电机原点回零模式实现

    硬件:Copley 驱动器ACJ-055-18+Maxon DCX-35L电机 1.原点回零方式简介: 有几种原点回零方法,每种方法建立:原点参考(限位或原点开关转换或编码器索引脉冲)运动方向以及索引 ...

  8. 问题记录 --Error parsing column 1 &lpar;Function&lowbar;Num&equals;10 - String&rpar;”

    当C#查询数据库出现Error parsing column ## 的时候,首先去看看数据库里面该字段是什么类型,然后在看看你在创建model 的时候是什么类型,如果model的类型和数据库字段类型不 ...

  9. HTML 转义字符对应表

    <%@ tag language="java" pageEncoding="UTF-8" %> <%@ attribute name=&quo ...

  10. 分析&OpenCurlyDoubleQuote;HTTP500内部服务器错误”解决方法

    系统中出现的一些故障是用户最不想看到的,有时候遇到一些故障都到折腾个大半天才能够搞定.打开网站出现了HTTP500内部服务器错误的提示,无法法查看错误的详细信息,用户也没办法根据具体的问题来解决,这对 ...