蓝桥杯 小朋友崇拜圈 国C
·
大概题意:有N个小朋友,编号从1到N 2行输入 第一行N 第二行N个数 分别代表1到N位小朋友崇拜的对象
每位小朋友都有一个小小的要求,那就是需要自己崇拜的那位小朋友坐在自己的右手边,当然每个小朋友也可以崇拜自己
简单想象一下,会有三种情况:一 不成圈,那么人数自然为0 ;二 成一个环 但是哪些小朋友参与成环不确定;
三 成很多环,需要寻找最大环
具体思路:不确定环的生成由哪些小朋友组成,所以对于每一位小朋友都当作环的起始点,使用dfs(int index)进行判断。
dfs:为了确定是哪位小朋友,需要传参index。然后每次使用dfs都需要对vis[]数组进行初始化,避免之前的深搜过程影响本次查找。
为了构成环,使用while循环不断的寻找下一个被崇拜的人 直到下一个人被访问过。退出循环之后需要确定的是,最后一个由于被访问过
而导致退出循环的小朋友,是不是本次进行深搜的小朋友,如果是,那么说明深搜成功,否则返回0
缺点:本次N的范围3~10e5 而我采用的方法时间复杂度达到O(n^2)通过本题只能说明大部分用例都会成很多小环,导致while循环提前终止。
下面是完整代码
import java.util.Scanner;
public class Main {
static int n;
static int arr[];
static boolean vis[];
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int max=0;
n=sc.nextInt();
arr=new int[n+1];
for(int i=1;i<=n;i++){
arr[i]=sc.nextInt();
}
for(int i=1;i<=n;i++){
int len=dfs(i);
max=max>=len?max:len;
}
System.out.println(max);
}
public static int dfs(int index){
int len=1;
vis=new boolean[n+1];
vis[index]=true;
int next=arr[index];
while(!vis[next]){
vis[next]=true;
next=arr[next];
len++;
if(len>n){
return -1;
}
}
if(next==index)
return len;
else
return 0;
}
}
更多推荐



所有评论(0)