1.小朋友崇拜圈

最开始，题主使用dfs实现拓扑排序，但是最后发现自己无法在遍历过程中记录每个节点（小朋友）的出度，导致后续找找最大环时不能确定函数的入口（题主太菜，找不到有效的方法）。该实现方法pass！
后面临时恶补使用bfs，利用Queue（队列）的方法实现拓扑排序，最后成功将此题解决。
image.png
输入：

9 3 4 2 5 3 8 4 6 9

输出：

4

1.1思路分析

首先思考，怎么确定哪几个元素组成环？总不能手画把（手动滑稽）
由题可知，所谓小朋友崇拜圈抽象看就是一个有向有环图，环可以类比为一个首尾咬住的贪吃蛇，蛇身上的每一个节点都指向下一个节点，最终，我们的指针从头开始遍历到尾，最后又会和头相遇——这就是环。在环中，每一个节点的入度都为1，那么我们可以使用拓扑排序得到所有入度为1的点，我们要找的最大环，就在里面。
怎么找最大环？搜索！dfs搜到底就完了，递归的退出条件就是当首位相等（表示把当前环走完了一遍）。

1.2代码

1.2.1基于bfs的拓扑排序

  1. List<Integer>[] graph=buildGraph();//邻接表
  2. int[] indegree=new int[N];
  3. int[] res=new int[N];//拓扑排序结果
  4. Queue<Integer> q=new LinkedList<>();
  5. for(int i=0;i<indegree.length;i++){
  6.     if(indegree[i]==0){
  7.         q.offer(i);
  8.     }
  9. }
  10. int count=0;
  11. while(!q.isEmpty()){
  12.     int cur=q.poll();
  13.     res[count]=cur;
  14.     count++;
  15.     for(int next:graph){
  16.         //由于该点被移除，那么该点的下一节点的入读都要减1
  17.         indegree[next]--;
  18.         if(indegree[next]==0){
  19.             q.offer(next);
  20.         }
  21.     }
  22. }
  23. return res;//res中就是拓扑排序的结果

1.2.2基于dfs的拓扑排序

  1. List<Integer>[] graph=buildGraph;
  2. List<Integer> Path=new LinkedList<>();
  3. boolean[] vis=new boolean[N];//记录是否重复遍历
  4. boolean[] onPath=new boolean[N];//记录堆栈的遍历情况，有重复说明有环
  6. void main(){
  7.     for(int i=0;i<N;i++){
  8.         dfs(vis,graph,i);
  9.     }
  10.     Collections.reverse(Path);//后序遍历反转的结果就是拓扑排序
  11. }
  13. void dfs(boolean[] vis,List<Integer>[] graph,int start){
  14.     if(vis[start]){
  15.         return;
  16.     }
  17.     vis[start]=true;
  18.     onPath[start]=true;
  19.     for(int next:graph[start]){
  20.         dfs(vis,graph,next);
  21.     }
  22.     Path.add(start);
  23.     vis[start]=false;
  24. }

1.2.3完整代码

  1. package lanqiao;
  3. import java.util.LinkedList;
  4. import java.util.List;
  5. import java.util.Queue;
  6. import java.util.Scanner;
  8. public class Main2 {
  9.     static int max = 0;
  10.     static int circle = 1;
  12.     public static void main(String[] args) {
  13.         // TODO Auto-generated method stub
  14.         Scanner scan = new Scanner(System.in);
  15.         int N = scan.nextInt();
  16.         int[] indegree = new int[N + 1];
  17.         int[] res = new int[N];// 拓扑排序结果
  18.         int[] arr = new int[N + 1];
  19.         boolean[] vis = new boolean[N + 1];
  20.         List<Integer>[] list = new LinkedList[N + 1];
  21.         scan.nextLine();
  22.         for (int i = 1; i <= N; i++) {
  23.             int tmp = scan.nextInt();
  24.             arr[i] = tmp;
  25.             indegree[arr[i]]++;
  26.         }
  27.         for (int i = 1; i < list.length; i++) {
  28.             list[i] = new LinkedList<Integer>();
  29.             list[i].add(arr[i]);
  30.         }
  31.         Queue<Integer> q = new LinkedList<Integer>();
  32.         for (int i = 1; i < indegree.length; i++) {
  33.             if (indegree[i] == 0) {
  34.                 q.offer(i);
  35.             }
  36.         }
  37.         int count = 0;
  38.         while (!q.isEmpty()) {
  39.             int tmp = q.poll();
  40.             res[count] = tmp;
  41.             count++;
  42.             for (int next : list[tmp]) {
  43.                 indegree[next]--;
  44.                 if (indegree[next] == 0) {
  45.                     q.offer(next);
  46.                 }
  47.             }
  48.         }
  49.         //dfs寻找最大环
  50.         for (int s = 1; s < arr.length; s++) {
  51.             if (indegree[s] != 0) {
  52.                 circle = 1;
  53.                 // vis[s] = true;
  54.                 dfs(arr, s, arr[s]);
  55.             }
  56.         }
  57.         System.out.println(max);
  58. //        for (int j = 1; j < indegree.length; j++) {
  59. //            System.out.print(indegree[j] + " ");
  60. //        } // indegree数组 中入度为0的即表示不在环中0 1 1 1 1 1 0 1 1
  61. //            // 1 7不在环中
  63.     }
  65.     public static void dfs(int[] arr, int now, int next) {
  66.         if (next == now) {
  67.             max = Math.max(max, circle);
  68.             return;
  69.         }
  70.         circle++;
  71.         dfs(arr, now, arr[next]);
  72.     }
  74. }