【题目来源】
蓝桥云课：1.小朋友崇拜圈 - 蓝桥云课 (lanqiao.cn)
【题目描述】
班里 \(N\) 个小朋友，每个人都有自己最崇拜的一个小朋友(也可以是自己)。
在一个游戏中，需要小朋友坐一个圈，每个小朋友都有自己最崇拜的小朋友在他的右手边。
求满足条件的圈最大多少人?
小朋友编号为 \(1,2,3,...N\)。
【输入】
输入第一行，一个整数 \(N(3<N<10^5)\).
接下来一行 \(N\) 个整数，由空格分开。
【输出】
要求输出一个整数，表示满足条件的最大圈的人数。
【输入样例】
9
3 4 2 5 3 8 4 6 9
【输出样例】
4
【算法标签】
《蓝桥云课 182 小朋友崇拜圈》 #2018# #省赛# #DFS#
【代码详解】
# 课堂练习
import sys
#扩栈：递归层数过大，需要设置最大栈空间
sys.setrecursionlimit(100000)def dfs(x, length):#记录走到x的步长为lengthvis[x] = length#接下来要走下一个点#判断下一个点是否走过if vis[a[x]] != 0:#此时存在环global ansans = max(ans, length-vis[a[x]]+1)else:dfs(a[x], length+1)n = int(input())
a = [0] + list(map(int, input().split()))
#标记数组：vis[x]表示点x的步数
vis = [0] * (n+1)
ans = 0
for i in range(1, n+1):#对于每个单独的连通块，都要做一遍dfsif vis[i] == 0:dfs(i, 1)
print(ans)
【运行结果】
9
3 4 2 5 3 8 4 6 9
4