题目描述
以前有个孩子,他分分钟都在碎碎念。不过,他的念头之间是有因果关系的。他会在本子里记录每一个念头,并用箭头画出这个念头的来源于之前的哪一个念头。翻开这个本子,你一定会被互相穿梭的箭头给搅晕,现在他希望你用程序计算出这些念头中最长的一条因果链。
将念头从1到n编号,念头i来源于念头from[i],保证from[i]<i,from[i]=0表示该念头没有来源念头,只是脑袋一抽,灵光一现。
输入
第一行一个正整数n表示念头的数量
接下来n行依次给出from[1],from[2],…,from[n]
输出
共一行,一个正整数L表示最长的念头因果链中的念头数量
样例输入
8 0 1 0 3 2 4 2 4
样例输出
3
本题刚开始理解错误,后来才反应回来由于这个链要形成总是有from[i] < i
所以就可以从后往前了,当然了,从前往后也可以
我们可以看到在测试数据中
from[9] = {0, 0, 1, 0, 3, 2, 4, 2, 4}
假设t为数组下标,则有
from[1] = 0 ,t = 1
from[2] = 1 ,t = 2
from[3] = 0 ,t = 3
from[4] = 3 ,t = 4
from[5] = 2 ,t = 5
from[6] = 4 ,t = 6
from[7] = 2 ,t = 7
from[8] = 4 ,t = 8
那么斜着看则有
from[1] → from[2] →from[5]
from[1] → from[2] →from[7]
from[3] → from[4] →from[6]
from[3] → from[4] →from[8]
贴个代码:
#include<stdio.h>
int a[1005];
int main()
{
int n, g, big = 0;
scanf("%d", &n);
for(int i = 1; i <= n; i++)
scanf("%d", &a[i]);
for(int i = 1; i <= n; i++){
int t = i, g = 1;
while(a[t] < t && a[t] != 0){
g++;
t = a[t];
}
if(big < g)
big = g;
}
printf("%d", big);
return 0;
}