题目描述：
本题给定一个庞大家族的家谱，要请你给出最小一辈的名单。
输入格式：
输入在第一行给出家族人口总数 N（不超过 100 000 的正整数） —— 简单起见，我们把家族成员从 1 到 N 编号。随后第二行给出 N 个编号，其中第 i 个编号对应第 i 位成员的父/母。家谱中辈分最高的老祖宗对应的父/母编号为 -1。一行中的数字间以空格分隔。
输出格式：
首先输出最小的辈分（老祖宗的辈分为 1，以下逐级递增）。然后在第二行按递增顺序输出辈分最小的成员的编号。编号间以一个空格分隔，行首尾不得有多余空格。
输入样例：
9 2 6 5 5 -1 5 6 4 7
输出样例：
4 1 9
解题思路：
使用数组存，用递归思想找每个人的祖先并记录每一个人的辈分数。
注：使用c++语言就可以使用bfs很快就出来了，c++的vector存放数据很灵活。小字辈 bfs搜索
代码（超时）
优化前：
package text2; import java.util.Scanner; public class 小字辈 { public static void main(String[] args) { // TODO Auto-generated method stub Scanner scanner = new Scanner(System.in); int n = scanner.nextInt(); int a[] = new int[n+1]; int b[]= new int[n+1]; int max=1; for(int i=1;i<=n;i++) { a[i] = scanner.nextInt(); } for(int i=1;i<=n;i++) { // int t=0;//临时记录辈分 int x=i; b[i]=1; while(a[x]!=-1) { b[i]++; x=a[x];//往上找 } if(b[i]>max) max = b[i]; } System.out.println(max); int flag=0; for(int i=1;i<=n;i++) { if(b[i]==max) { if(flag==0) { System.out.print(i); flag++; }else { System.out.print(" "+i); } } } } }
优化后：
package text2; import java.util.ArrayList; import java.util.Scanner; import java.util.Vector; public class 小字辈 { static int a[] = new int[100005]; static int b[]= new int[100005]; public static void main(String[] args) { // TODO Auto-generated method stub // Vector<Integer> a[][] = new Vector<Integer>;/ // ArrayList<Integer> a = new ArrayList<Integer>(); Scanner scanner = new Scanner(System.in); int n = scanner.nextInt(); int max=1; for(int i=1;i<=n;i++) { a[i] = scanner.nextInt(); } for(int i=1;i<=n;i++) { int t=0; t=Find(i); if(t>max) max = t; } System.out.println(max); int flag=0; for(int i=1;i<=n;i++) { if(b[i]==max) { if(flag==0) { System.out.print(i); flag++; }else { System.out.print(" "+i); } } } } public static int Find(int x) { if(b[x]!=0) return b[x]; else if(a[x]==-1) return b[x]=1; else { return b[x]=Find(a[x])+1; } } }
