菜菜ccEL

用户名：uq_98515084648

访问量：2830

签　名：

等　　级
排　　名	2089
经　　验	2463
参赛次数	0
文章发表	30
年　　龄	0
在职情况	学生
学　　校
专　　业	计算机科学与技术

　　自我简介：

TA的其他文章

蓝桥杯2018年第九届真题-全球变暖-JAVA【参考优质题解】-详细注释
浏览：113

蓝桥杯2018年第九届真题-航班时间-JAVA解法-简单易懂
浏览：126

蓝桥杯2018年第九届真题-日志统计-JAVA双指针-分情况讨论
浏览：44

你可能喜欢

A+B for Input-Output Practice (III) （C语言代码）

蓝桥杯2018年第九届真题-小朋友崇拜圈-dfs暴力

　　作者: 菜菜ccEL　　　　发表时间：2023-04-05 15:59:09 浏览：48　|　评论：0　

原题链接：蓝桥杯2018年第九届真题-小朋友崇拜圈

import java.io.BufferedReader;
    import java.io.IOException;
    import java.io.InputStreamReader;
    import java.io.StreamTokenizer;
    import java.util.ArrayList;
    import java.util.List;
    
    public class Main {
    	static BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
    	static StreamTokenizer st = new StreamTokenizer(reader);
    	static int nextInt() throws IOException {
    		st.nextToken();
    		return (int)st.nval;
    	}
    	public static int n; //小朋友数量
    	public static int max = Integer.MIN_VALUE; //存储结果
    	public static int[] nums; //nums[i]=val表示第i个小朋友崇拜的人为val
    	public static boolean[] vis; //标记每个小朋友是否被访问
    	public static void main(String[] args) throws IOException {
    		//输入
    		n = nextInt();
    		nums = new int[n+2];
    		vis = new boolean[n+2];
    		for(int i=1;i<=n;i++)
    			nums[i] = nextInt();
    		//对未访问的小朋友dfs，已经访问过的说明已经形成闭环，不用再访问
    		for(int i=1;i<=n;i++) {
    			if(!vis[i]) dfs(i);
    		}
    		//输出结果
    		System.out.println(max); 
    		
    	}
    	public static void dfs(int x) { //x表示起点序号
    		List<Integer>res = new ArrayList<>(); //存储当前环中小朋友的序号
    		res.add(x); //加入起点
    		int cnt; //定义环中有多少人
    		while(true) {
    			int next = nums[x]; //下个小朋友的序号
    			if(!vis[next]) { //若未访问，直接访问并加入到res中
    				x = next; 
    				vis[x] = true;
    				res.add(x);
    			}else { //当前要访问的小朋友已经被访问，说明已形成环
    				//从next出发找圈中有多少人
    				cnt = res.size()-res.indexOf(new Integer(next));
    				if(cnt>max) max = cnt; //更新结果
    				break; //结束循环
    			}
    		}	
    	}
    	
    
    }
    ``

0.0分

0 人评分

看不懂代码解释一下代码? 或者生成一段代码？试试AI编程助手吧

菜菜ccEL

TA的其他文章

你可能喜欢

A+B for Input-Output Practice (III) （C语言代码）

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

母牛的故事（C语言代码）

校门外的树（C语言代码）

【蟠桃记】（C语言代码）

蓝桥杯2018年第九届真题-小朋友崇拜圈-dfs暴力

评论区

精彩推荐

C语言程序设计教程（第三版）课后习题5.7 （C语言代码）

简单的a+b （C语言代码）

C语言程序设计教程（第三版）课后习题1.6 （C语言代码）

C语言训练-数字母（C语言代码）

C语言训练-求s=a+aa+aaa+aaaa+aa...a的值（C语言代码）

WU-陶陶摘苹果2 （C++代码）

WU-C语言程序设计教程（第三版）课后习题11.12 （C++代码）（想学链表的小伙伴可以看看）

C语言程序设计教程（第三版）课后习题8.5 （C语言代码）

C语言程序设计教程（第三版）课后习题5.7 （C语言代码）

Hello, world! （C语言代码）

菜菜ccEL

TA的其他文章

你可能喜欢

A+B for Input-Output Practice (III) （C语言代码）

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

母牛的故事 （C语言代码）

校门外的树 （C语言代码）

【蟠桃记】 （C语言代码）

蓝桥杯2018年第九届真题-小朋友崇拜圈-dfs暴力

评论区

精彩推荐

C语言程序设计教程（第三版）课后习题5.7 （C语言代码）

简单的a+b （C语言代码）

C语言程序设计教程（第三版）课后习题1.6 （C语言代码）

C语言训练-数字母 （C语言代码）

C语言训练-求s=a+aa+aaa+aaaa+aa...a的值 （C语言代码）

WU-陶陶摘苹果2 （C++代码）

WU-C语言程序设计教程（第三版）课后习题11.12 （C++代码）（想学链表的小伙伴可以看看）

C语言程序设计教程（第三版）课后习题8.5 （C语言代码）

C语言程序设计教程（第三版）课后习题5.7 （C语言代码）

Hello, world! （C语言代码）

母牛的故事（C语言代码）

校门外的树（C语言代码）

【蟠桃记】（C语言代码）

　　评论区

C语言训练-数字母（C语言代码）

C语言训练-求s=a+aa+aaa+aaaa+aa...a的值（C语言代码）