蓝桥杯2018年第九届真题-小朋友崇拜圈-题解（Java代码）

如果题目没看懂，没看懂就对了，因为题目并不完整，下面是完整题目。

假设输入的n个数字存储在 nums[]中，那么nums[i]表示第i个小朋友崇拜的是 nums[i]。

这题是找出最大的那个圈中小朋友的个数，从这个图可以看出共有三个圈，其中从2开始到2结束的圈最大。

既然第i个小朋友的下一个小朋友是nums[i] ,

那么就根据i得到nums[i],根据nums[i]得到nums[i]崇拜的小朋友，

next= nums[i] 下一个小朋友

这里使用dp[]存储小朋友个数，dp[next]=dp[i]+1;

直到遇到一个已经判断过的小朋友，也就是dp[i]!=0时退出循环。

两种写法，思路相同

循环法的耗时更短，因为使用set记录已经走过的点，去除很多重复的运算。

循环法，搜索法

1，循环法，

import java.util.HashSet;
import java.util.Scanner;
import java.util.Set;
import java.util.TreeSet;

public class Main {

	/**
	 * @param args
	 */
	public static  Set<Integer> vis=new HashSet<Integer>();//记录已经走过的点
	public static void main(String[] args) {
		Scanner sc=new Scanner(System.in);
        int n = sc.nextInt();
        int[] nums = new int[n+1];
        for (int i = 1; i <=n; i++) {
            nums[i] = sc.nextInt();
        }
       
        int max = 0;
        for (int i = 1; i <=n; i++) {
			int dp[]=new int[n+1];//当前 到达第i个小朋友的步数
			if (vis.contains(i)) {//不用找了
				continue;
			}
			max=Math.max(check(nums, dp, i), max);
		}
        System.out.println(max);
        
    }
	
	public static int check(int nums[],int dp[],int step) {
		vis.add(step);//走过step点
		dp[step]=1;
		while (dp[nums[step]]==0) {//没走过
			int next=nums[step];
			dp[next]=dp[step]+1;
			step=next;
			vis.add(step);//走过step点
		}
		return dp[step]-dp[nums[step]]+1;
	}



	
}

搜索

import java.util.HashSet;
import java.util.Scanner;
import java.util.Set;
import java.util.TreeSet;

public class Main {

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		Scanner sc=new Scanner(System.in);
        int n = sc.nextInt();
        int[] nums = new int[n+1];
        for (int i = 1; i <=n; i++) {
            nums[i] = sc.nextInt();
        }
       
        int max = 0;
        for (int i = 1; i <=n; i++) {
			int dp[]=new int[n+1];//当前 到达第i个小朋友的步数
			dp[i]=1;
			max=Math.max(dfs(nums, dp, i), max);
		}
        System.out.println(max);
        
    }
	
	public static int dfs(int nums[],int dp[],int step) {
		int next=nums[step];//下一个点
		if (next==step) {
			return 0;
		}
		if (dp[next]!=0) {
			return dp[step]-dp[next]+1;//得到循环的大小
		}else {
			dp[next]=dp[step]+1;
			int _ans= dfs(nums, dp, next);
			return _ans;
		}
	}



	
}

搜索2，

将已经得到的答案存储起来，下一次直接可以直接使用。优化速度。

import java.util.HashSet;
import java.util.Scanner;
import java.util.Set;
import java.util.TreeSet;

public class Main {

	/**
	 * @param args
	 */
	public static int tAns[];//将已知的答案记录下来
	public static void main(String[] args) {
		Scanner sc=new Scanner(System.in);
        int n = sc.nextInt();
        int[] nums = new int[n+1];
        tAns=new int[n+1];
        for (int i = 1; i <=n; i++) {
            nums[i] = sc.nextInt();
        }
       
        int max = 0;
        for (int i = 1; i <=n; i++) {
			int dp[]=new int[n+1];//当前 到达第i个小朋友的步数
			dp[i]=1;
			if (tAns[i]!=0) {
				max=Math.max(tAns[i], max);
			}else {
				max=Math.max(dfs(nums, dp, i), max);
			}
			
		}
        System.out.println(max);
        
    }
	
	
	public static int dfs(int nums[],int dp[],int step) {
		int next=nums[step];//下一个点
		if (next==step) {
			return 0;
		}
		if (tAns[step]!=0) {//返回已知的答案
			return tAns[step];
		}
		if (dp[next]!=0) {
			return tAns[step]=dp[step]-dp[next]+1;//得到循环的大小
		}else {
			dp[next]=dp[step]+1;
			int _ans= dfs(nums, dp, next);
			return _ans;
		}
	}



	
}