班里 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] 构成的圈
再例如:
输入:
- 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
- import java.util.ArrayList;
- import java.util.Scanner;
public class Main 小朋友 {
- static Scanner sc = new Scanner(System.in);
- static int n = sc.nextInt();
- static int max = 0;
- static int[] nums = new int[n];
- public static void main(String[] args) {
- for (int i = 0; i <n; i++) {
- nums[i] = sc.nextInt();
- }
- for (int i = 0; i < nums.length; i++)
- {
- ArrayList<Integer> list = new ArrayList<Integer>();
- f(nums[i],list);
- }
- System.out.println(max);
- }
- static void f(int k,ArrayList<Integer> list)
- {
- int cnt = 0;
- while (!list.contains(k))
- {// 集合中有没有第 i 个小朋友
- System.out.print(k+" ");
- list.add(k);// 添加崇拜的人
- k = nums[k - 1];// 找到当前崇拜的人
- cnt++;// 崇拜人的人数
- if (cnt> max)
- {
- max = cnt;// 找出人数最多的
- }
- }
- System.out.println();
- }
- }
来源: http://www.bubuko.com/infodetail-3437918.html