看了网上发的一些答案,感觉都不是很好,也有很多错的,所以发表一下自己的,这次确实比较简单。
1.从第一个点到最后一个点依次dfs,依靠状态数组vis[]进行判断是否终止继续遍历。
2.如果从某点开始遍历形成环最终回到该点,则将此环长度与已记录的最大环长度比较,取大的。如果从某点开始遍历形成环最终未回到该点,则该环长度直接跳过,不予比较。
import java.util.Scanner; public class 小朋友崇拜圈 { static boolean[] vis; static int max = -1; static int n; static int[] a; public static void main(String[] args) { Scanner sc = new Scanner(System.in); n = sc.nextInt(); a = new int[n + 1]; vis = new boolean[n + 1]; for (int i = 1; i <= n; i++) a[i] = sc.nextInt(); for (int i = 1; i <= n; i++) { dfs(i); } System.out.println(max); } private static void dfs(int p) { int sum = 0; int t = p; while (!vis[t]) { vis[t] = true; t = a[t]; sum++; } if (t == p) { if (sum > max) max = sum; } vis = new boolean[n + 1]; } }
记得收藏!