试题 算法提高 分分钟的碎碎念
提交此题 评测记录
资源限制
时间限制：1.0s 内存限制：256.0MB
问题描述
以前有个孩子，他分分钟都在碎碎念。不过，他的念头之间是有因果关系的。他会在本子里记录每一个念头，并用箭头画出这个念头的来源于之前的哪一个念头。翻开这个本子，你一定会被互相穿梭的箭头给搅晕，现在他希望你用程序计算出这些念头中最长的一条因果链。
将念头从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
样例说明
最长的因果链有：
1->2->5 (from[5]=2,from[2]=1,from[1]=0)
1->2->7 (from[7]=2,from[2]=1,from[1]=0)
3->4->6 (from[6]=4,from[4]=3,from[3]=0)
3->4->8 (from[8]=4,from[4]=3,from[3]=0)
数据规模和约定
1<=n<=1000
解题思路：求树的最深路径，也就是 用BFS算法 求最大层数。
AC代码如下：
#include <iostream>
#include <vector>
#include <string.h>
#include <queue>
using namespace std;
vector< vector<int> > G(1010);
int n;
int vis[1010];
int from[1010];
int maxL=0;
void Read(){
cin>>n;
memset(from,0,sizeof(from));
for(int i=1;i<=n;i++){
int fro;
cin>>fro;
from[i]=fro;
if(fro!=0)
G[fro].push_back(i);
}
}
void BFS(int S){
queue<int> Q;
Q.push(S);
vis[S]=1;
int last=S;
int level=0;
int tail=0;
while(!Q.empty()){
int V=Q.front();
Q.pop();
for(int i=0;i<G[V].size();i++){
int to=G[V][i];
if(vis[to]==0){
vis[to]=1;
Q.push(to);
tail=to;//更新尾结点
}
}
if(V==last){
level++;
last=tail;//last 每一层的最后一个节点
}
}
maxL=max(maxL,level);
}
void opt(){
for(int i=1;i<=n;i++){
if(from[i]==0){
memset(vis,0,sizeof(vis));
BFS(i);
}
}
}
int main(int argc, char** argv) {
Read();
opt();
cout<<maxL<<endl;
return 0;
}