标题：小朋友崇拜圈
班里N个小朋友，每个人都有自己最崇拜的一个小朋友（也可以是自己）。
在一个游戏中，需要小朋友坐一个圈，
每个小朋友都有自己最崇拜的小朋友在他的右手边。
求满足条件的圈最大多少人？
小朋友编号为1,2,3,...N
输入第一行，一个整数N（3<N<100000）
接下来一行N个整数，由空格分开。
要求输出一个整数，表示满足条件的最大圈的人数。
例如：
输入：
9
3 4 2 5 3 8 4 6 9
则程序应该输出：
4
解释：
如图p1.png所示，崇拜关系用箭头表示，红色表示不在圈中。
显然，最大圈是[2 4 5 3] 构成的圈
3.png
再例如：
输入：
30
22 28 16 6 27 21 30 1 29 10 9 14 24 11 7 2 8 5 26 4 12 3 25 18 20 19 23 17 13 15
程序应该输出：
16
资源约定：
峰值内存消耗（含虚拟机） < 256M
CPU消耗 < 1000ms
请严格按要求输出，不要画蛇添足地打印类似：“请您输入...” 的多余内容。
所有代码放在同一个源文件中，调试通过后，拷贝提交该源码。
不要使用package语句。不要使用jdk1.7及以上版本的特性。
主类的名字必须是：Main，否则按无效代码处理。
解析：
解题思路如下：
1、找规律理解崇拜关系,将一行整数存入数组arr，假设当前数组元素值为num,则a崇拜的人为arr[num-1]。
2、定义变量max保存最长崇拜圈。
3、遍历数组进行寻找，找到崇拜的人存入集合中且集合内未有重复元素则计数器加1
4、每次遍历后比较计数器count和max，将最大的数保存为max。
5、输出max。
Scanner input = new Scanner(System.in);
int sum = input.nextInt(); //输入总人数
int[] arr = new int[sum];
//输入n个整数存入数组
for (int i = 0; i < arr.length; i++) {
arr[i] = input.nextInt();
}
int max = 0; //假设最长崇拜圈人数为0
//遍历数组，以每个数组元素为起点，不停找崇拜的人
for (int i = 0; i < arr.length; i++) {
int num = arr[i]; //获取当前数字
int count = 0; //记录当前崇拜圈人数
List<Integer> listInt = new ArrayList<Integer>(); //定义集合保存崇拜圈元素
while(true)
{
if(listInt.contains(num)) //当在集合中找到了元素，证明崇拜圈结束
break;
listInt.add(num); //将当前人，加入崇拜圈集合
num = arr[num-1]; //将当前人崇拜的人，设置为当前，在通过while循环继续向后查找
count++; //当前崇拜圈人数+1
if(count > max)
max = count;
}
}
System.out.println(max);
网友评论