题目描述

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

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

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

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

输入格式

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

输出格式
输出一个整数，表示满足条件的最大圈的人数。
数据范围

3<N<100000

样例

输入样例1：
9
3 4 2 5 3 8 4 6 9

输出样例1：
4

dfs

C++ 代码

#include<iostream>
#include<vector>
#include<algorithm>
#include<climits>
using namespace std;

const int MAX = 100001;
int n;
int chi[MAX];
vector<int> vc;
bool visited[MAX]={};

void dfs(int next){
    if(visited[next]){
        int length=0;
        for(int i=0;i<vc.size();i++){
            if(next == vc[i]){
                length = vc.size()-i;
            }
        }
        chi[0] = max(chi[0],length);
        return ;
    }
    vc.push_back(next);
    visited[next] = true;
    dfs(chi[next]);
}

void solve(){
    for(int i=1;i<=n;i++){
        if(!visited[i]){
            visited[i] = true;
            vc.push_back(i);
            dfs(chi[i]);
            vc.clear();
        }

    }
}

int main(){

    scanf("%d", &n);

    for(int i=1;i<=n;i++){
        scanf("%d",&chi[i]);    
    }
    chi[0]=INT_MIN;
    solve();
    printf("%d\n" ,chi[0]);
    return 0;
}