问题 2283: [蓝桥杯][2018年第九届真题]小朋友崇拜圈

时间限制: 1Sec 内存限制: 128MB 提交: 44 解决: 29
题目描述
班里N个小朋友，每个人都有自己最崇拜的一个小朋友（也可以是自己）。
在一个游戏中，需要小朋友坐一个圈，
每个小朋友都有自己最崇拜的小朋友在他的右手边。
求满足条件的圈最大多少人？

小朋友编号为1,2,3,…N

输入
输入第一行，一个整数N（3<N<100000）
接下来一行N个整数，由空格分开。
输出
要求输出一个整数，表示满足条件的最大圈的人数。
样例输入

9
3 4 2 5 3 8 4 6 9

样例输出

4

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<map>
#include<vector>
#include<queue>
#include<set>
#define IL inline
#define x first
#define y second
typedef long long ll;
using namespace std;
const	int N=100010;
int duin[N];
int a[N];
bool st[N];
int main()
{
	int n;
	cin>>n;
	for(int i=1;i<=n;i++)
	{cin>>a[i];
	duin[a[i]]++;
	}
	for(int i=1;i<=n;i++)//先把度为0的点删掉，然后连锁反应
	{
		if(st[i])	continue;
		if(duin[i]==0)	
		{
			st[i]=true;
			int t=a[i];
			while(--duin[t]==0)
			{
				st[t]=true;
				t=a[t];
			}
		}
	}
	int maxv=0;
	for(int i=1;i<=n;i++)
	{
		if(st[i])	continue;
		int tt=1;
		int t=a[i];
		while(i!=t)
		{
			tt++;
			st[t]=true;
			t=a[t];
		}
		maxv=max(maxv,tt);
	}
	cout<<maxv<<endl;
    return 0;
}