2018年Java方向C组第九题

标题：小朋友崇拜圈

班里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);