大概题意:有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;
    }
}
Logo

开源鸿蒙跨平台开发社区汇聚开发者与厂商,共建“一次开发,多端部署”的开源生态,致力于降低跨端开发门槛,推动万物智联创新。

更多推荐