[图论]求最小环的长度

信息传递

Description

有 nn 个同学（编号为 11 到 nn ）正在玩一个信息传递的游戏。在游戏里每人都有一个固定的信息传递对象，其中，编号为 ii 的同学的信息传递对象是编号为 T_iTi​ 的同学。

游戏开始时，每人都只知道自己的生日。之后每一轮中，所有人会同时将自己当前所知的生日信息告诉各自的信息传递对象（注意：可能有人可以从若干人那里获取信息， 但是每人只会把信息告诉一个人，即自己的信息传递对象）。当有人从别人口中得知自 己的生日时，游戏结束。请问该游戏一共可以进行几轮？

Input

共2行。

第1行包含1个正整数 n ，表示 n 个人。

第2行包含 n 个用空格隔开的正整数 T1​,T2​,⋯⋯,Tn​ ，其中第 i 个整数 Ti​ 表示编号为 i 的同学的信息传递对象是编号为 Ti​ 的同学， Ti ​≤n 且 Ti​≠i 。

Output

$1个整数，表示游戏一共可以进行多少轮。$

Examples

Input

5
2 4 2 3 1

Output

3

 

正确解法：

很容易画出一个有向图，后来想一想，如何传递这个生日。

走一轮一条边，走出一个环的长度，游戏结束了。

那么这题所要求的就是最小环的长度。

一个图如何求最小环的长度呢？

从每个点的出度开始求，如果找了半天最终发现他的父亲就是他自己，那么这是一个环。长度就在递归的次数。

容易坑的一个点就是有一个 & 符号。目前为什么我还没有想出来qaq

 for(int i=1;i<=n;i++)
    {
        int xx;
        cnt=0;
        scanf("%d",&xx);
        if(getf(xx,cnt)==i)
            ans=min(ans,cnt);
        else
            fa[i]=xx;
    }

#include<iostream>
#include<cstdio>
#include<string>
#include<cstring>
#include<map>
#include<set>
#include<vector>
#include<queue>
#include<algorithm>
#include<cmath>
using namespace std;
typedef long long ll;
const int N=200000+10;
int n,fa[N],cnt;
int ans=99999999;
int getf(int x,int &cnt)
{
    cnt++;
    if(fa[x]==x)    return x;
    return getf(fa[x],cnt);
}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        fa[i]=i;
    for(int i=1;i<=n;i++)
    {
        int xx;
        cnt=0;
        scanf("%d",&xx);
        if(getf(xx,cnt)==i)
            ans=min(ans,cnt);
        else
            fa[i]=xx;
    }
    printf("%d\n",ans);
    return 0;
}