renqinghua

public class _2283小朋友崇拜圈
{
	private static int[] a;//保存数据
	private static int[] d;//存储入度
	private static int[] del;//标志小朋友是否可能在圈子中
	private static int n;

public static void main(String[] args)
	{
		Scanner scan=new Scanner(System.in);
		
		n=scan.nextInt();
		
		a=new int[n+5];
		d=new int[n+5];
		del=new int[n+5];
		
		for(int i=1;i<=n;i++)
		{
			int t=scan.nextInt();
			a[i]=t;
			d[t]++;//1号崇拜3号，则被崇拜的3号入度+1
			
		}
		
		ff();//剔除掉入度为0的小朋友，他们不可能在任何一个圈中
		
		int ans=0;
		
		//剔除掉不在圈中的人后，剩下的小朋友肯定在某一个圈中了
		for(int i=1;i<=n;i++)
		{
			if(del[i]==1)//有被剔除的人
				continue;
			
			del[i]=1;//从这个人开始去找圈，这是也要排除掉，防止重复找
			int pos=i,sum=1;
			//如果某个人崇拜的编号是我们出发的人的编号，则构成了一个圈
			while(a[pos]!=i)
			{
				sum++;
				del[pos]=1;
				pos=a[pos];
			}
			ans=Math.max(ans, sum);
			
		}
		
		System.out.println(ans);
		
		
		
		scan.close();

}

private static void ff()
	{
		Queue<Integer> queue=new LinkedList<>();
		for(int i=1;i<=n;i++)
		{
			//入度为0的小朋友，表示没有被人崇拜
			if(d[i]==0)
			{
				del[i]=1;//剔除
				d[a[i]]--;//其崇拜的小朋友入度-1
				queue.offer(i);//入度为0入队
			}
		}
		
		while(!queue.isEmpty())
		{
			int t=queue.poll();//出队并删除
			
			int t2=a[t];//t2表示被编号t崇拜的人
			//如果当前编号为t的人崇拜的编号为t2的人入度为0,则表示只有t崇拜他t2，则t2也不可能在任何一个圈中
			if(d[t2]==0)
			{
				del[t2]=1;//剔除
				queue.offer(t2);
				if(d[a[t2]]>0)
					d[a[t2]]--;
				//这边其实就是在重复上面for循环的内容,
				
			}
			
		}
		
	}

}

```

0.0分

0 人评分

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

renqinghua

TA的其他文章

你可能喜欢

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

2005年春浙江省计算机等级考试二级C 编程题(1) （C语言代码）

2004年秋浙江省计算机等级考试二级C 编程题(2) （C语言代码）

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

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

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

评论区

精彩推荐

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

买不到的数目（C++代码）

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

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

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

链表数据求和操作（C语言代码）

C二级辅导-等差数列（C语言代码）

1162答案错误，为什么

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

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

renqinghua

TA的其他文章

你可能喜欢

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

2005年春浙江省计算机等级考试二级C 编程题(1) （C语言代码）

2004年秋浙江省计算机等级考试二级C 编程题(2) （C语言代码）

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

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

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

评论区

精彩推荐

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

买不到的数目 （C++代码）

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

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

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

链表数据求和操作 （C语言代码）

C二级辅导-等差数列 （C语言代码）

1162答案错误，为什么

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

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

　　评论区

买不到的数目（C++代码）

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

链表数据求和操作（C语言代码）

C二级辅导-等差数列（C语言代码）