【蓝桥杯】小朋友崇拜圈

小朋友崇拜圈

班里 N N N个小朋友，每个人都有自己最崇拜的一个小朋友（也可以是自己）。

在一个游戏中，需要小朋友坐一个圈，每个小朋友都有自己最崇拜的小朋友在他的右手边。

求满足条件的圈最大多少人？

小朋友编号为 1 , 2 , 3 , ⋯ N 1,2,3,cdots N 1,2,3,⋯N。

输入描述
输入第一行，一个整数 N （ 3 < N < 1 0 5 ） N（3

接下来一行 N N N 个整数，由空格分开。

输出描述
要求输出一个整数，表示满足条件的最大圈的人数。

输入输出样例
示例
输入

93 4 2 5 3 8 4 6 9

输出

4

样例解释

如下图所示，崇拜关系用箭头表示，红色表示不在圈中。

显然，最大圈是 [ 2   4   5   3 ] [2 4 5 3] [2 4 5 3] 构成的圈。

思路

题目可以转化成求一个有向图中圈的最大边数问题每个小朋友看成是一个结点，崇拜关系看成是一条有向边，那么如果有 N N N 个小朋友，那么就会有 N N N 个结点， N N N 条有向边对于每个结点，可以观察得出：有且仅有一条出边，如果要形成圈的话，则必须有一条入边，则可知：没有入边的结点一定不是圈中的结点初始时先除去入边为 0 0 0 的结点，不予考虑，那么易知，剩下的结点一定构成若干个圈 d f s dfs dfs：参数有两个，一个是第 i i i 个小朋友，一个是第 i i i 个小朋友崇拜的小朋友若这两个小朋友一样的话，那么肯定是形成了一个圈，则此条件可以作为递归出口若这两个小朋友不一样，则继续 d f s dfs dfs ，直到这两个小朋友一样(初始化的数据已经保证)设置一个圈的边数的最大值，如果一次 d f s dfs dfs 搜出来的边数大于这个最大值，则更新最后输出最大值即可 代码如下

#include #include using namespace std;vector a;//小朋友数组，第i个小朋友崇拜第a[i]个小朋友vector vis;//是否已经被访问过vector flag;//是否有入边int max_circle;//边数的最大值int circle;//临时变量，减少递归开销int n;//小朋友个数void init() { scanf("%d", &n); a.resize(n + 1); vis.resize(n + 1, false); flag.resize(n + 1, false); for (int i = 1; i <= n; i++) { scanf("%d", &a[i]); flag.at(a[i]) = true;//为真表示有入边，否则没有 }}void dfs(int start_id, int next_id) { if (next_id == start_id) { max_circle = max(circle, max_circle); return; } vis.at(next_id) = true; circle++; dfs(start_id, a.at(next_id));}void solve() { for (int i = 1; i <= n; i++) { if (flag.at(i) && !vis.at(i)) { vis.at(i) = true; circle = 1; dfs(i, a.at(i)); } } printf("%dn", max_circle);}int main(void) { init(); solve(); return 0;}