蓝桥杯--小朋友崇拜圈（有向图求最大环）

题目描述

班里N个小朋友，每个人都有自己最崇拜的一个小朋友（也可以是自己）。
在一个游戏中，需要小朋友坐一个圈，
每个小朋友都有自己最崇拜的小朋友在他的右手边。
求满足条件的圈最大多少人？

小朋友编号为1,2,3,…N
输入第一行，一个整数N（3<N<100000）
接下来一行N个整数，由空格分开。

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

测试样例

• 输入：
  9
  3 4 2 5 3 8 4 6 9

• 则程序应该输出：
  4

• 输入：
  30
  22 28 16 6 27 21 30 1 29 10 9 14 24 11 7 2 8 5 26 4 12 3 25 18 20 19 23 17 13 15

• 程序应该输出：
  16

解题思路

每个小朋友都有一个最崇拜的人，然后求这个多个崇拜圈的最大人数。有向图找最大环，用拓扑排序预处理一下把入度为0的人check掉，这些都是不能在圈中的，剩下的必然是存在于某个圈中。dfs求每个圈的人数更新最大值。

代码

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cstdlib>
#include <vector>
#include <queue>

using namespace std;
const int maxn = (int)1e5;

int v[maxn],cnt