并查集求最短路
把每个同学看成一个点，信息的传递就是在他们之间连有向边，游戏轮数就是求最小环。
图论求最小环，我在里面看到了并查集。
假如说信息由A传递给B，那么就连一条由A指向B的边，同时更新A的父节点，A到它的父节点的路径长也就是B到它的父节点的路径长+1。
这样我们就建立好了一个图，之后信息传递的所有环节都按照这些路径。游戏结束的轮数，也就是这个图里最小环的长度。
如果有两个点祖先节点相同，那么就构成一个环，环的长度为两点到祖先节点的距离之和+1。

#include<cstdio>
#include<iostream>
using namespace std;
int f[200002],d[200002],n,minn,last;   //f保存祖先节点，d保存到其祖先节点的路径长。 
int fa(int x)
{
    if (f[x]!=x)                         //查找时沿途更新祖先节点和路径长。 
    {
        int last=f[x];                     //记录父节点（会在递归中被更新）。 
        f[x]=fa(f[x]);                     //更新祖先节点。 
        d[x]+=d[last];                     //更新路径长（原来连在父节点上）。 
    }
    return f[x];
}
void check(int a,int b)
{
    int x=fa(a),y=fa(b);                 //查找祖先节点。 
    if (x!=y) {f[x]=y; d[a]=d[b]+1;}     //若不相连，则连接两点，更新父节点和路径长。 
    else minn=min(minn,d[a]+d[b]+1);     //若已连接，则更新最小环长度。 
    return;
}
int main()
{
    int i,t;
    scanf("%d",&n);
    for (i=1;i<=n;i++) f[i]=i;           //祖先节点初始化为自己，路径长为0。 
    minn=0x7777777;
    for (i=1;i<=n;i++)
    {
        scanf("%d",&t);
        check(i,t);                        //检查当前两点是否已有边相连接。 
    }
    printf("%d",minn);
    return 0;
}

思路：**并查集**判断最小环。输入的每一条信息路径可以看作一条有向边，**答案则是所有环中最小环的长度**。用并查集一边合并图，**一边检查新增边的两点是否已经在一个root中。如果为真，则增加此边后就会成环。**此时环的大小为dis[x] + dis[y] + 1，即为所求答案的一个值。若为假则增加这条边。
维护并查集时引入了一个dis[]数组，记录**此节点到根节点**的距离（途径边数），初始化都为0（自己到自己，不存在边）。若根节点被并入成为另一个子图的儿子，**它的子节点的dis在Find的时候被更新**。若成功新并入一条边，新边**出发点的dis在Union的时候被更新**。
```c++
#include <iostream>
using namespace std;

int root[200001], dis[200001] = {0};
int n, mindis = 9999999;

void Init()
{
for(int i = 1; i <= n; i++)
root[i] = i;
return;
}
int Find(int x)
{
if(x == root[x])
return x;
int tempRoot = root[x];
root[x] = Find(root[x]);
dis[x] += dis[tempRoot];
return root[x];
}
bool Union(int x, int y)
{
int xRoot = Find(x);
int yRoot = Find(y);
if(xRoot != yRoot) {
root[xRoot] = yRoot;
dis[x] = dis[y] + 1;
return true;
} else {
mindis = min(mindis, dis[x] + dis[y] + 1);
return false;
}
}

int main()
{
cin >> n;
Init();
int ty;
for(int i = 1; i <= n; i++) {
cin >> ty;
Union(i, ty);
}
cout << mindis << endl;
return 0;
}

[这篇并查集教程写的还不错，大家可以看看。](http://m.blog.csdn.net/article/details?id=37968863)
最后庆祝自己第一次尝试NOIP原题兼第一次使用VIJOS一次性AC~~~

tarjan缩点,注意判断是否大小为1。

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cmath>
#define LL long long
using namespace std;
template <class _T> inline void read(_T &_x){
    int _t;bool _flag=0;
    while((_t=getchar())!='-'&&(_t<'0'||_t>'9'));
    if(_t=='-')_flag=1,_t=getchar();_x=_t-'0';
    while((_t=getchar())>='0'&&_t<='9')_x=_x*10+_t-'0';
    if(_flag)_x=-_x;
}
const int maxn=2e5+5;
int n,cnt,x,top,idx,num[maxn],S[maxn],f[maxn],low[maxn],dfn[maxn],head[maxn],ans=0x3f3f3f3f;
bool ins[maxn];
struct edge{
    int v,nxt;
}d[maxn];
inline void add(int a,int b){
    d[++cnt].v=b;d[cnt].nxt=head[a];head[a]=cnt;
}
int find(int x){
    return x==f[x]? x:f[x]=find(f[x]);
}
void tj(int u){
    int v;
    dfn[u]=low[u]=++idx;
    S[++top]=u;ins[u]=1;
    for(int i=head[u];i;i=d[i].nxt){
        v=d[i].v;
        if(!dfn[v]){
            tj(v);
            low[u]=min(low[v],low[u]);
        }
        else if(ins[v])low[u]=min(dfn[v],low[u]);
    }
    if(dfn[u]==low[u]){
        while(u!=v){
            v=S[top--];
            ins[v]=0;
            int f1=find(u),f2=find(v);
            f[f2]=f1;
            if(f1!=f2)num[f1]+=num[f2];
        }
    }
}
int main(){
    read(n);
    for(int i=1;i<=n;i++){
        read(x);
        add(i,x);
    }
    for(int i=1;i<=n;i++)f[i]=i,num[i]=1;
    for(int i=1;i<=n;i++)if(!dfn[i])tj(i);
    for(int i=1;i<=n;i++){
        int tmp=num[find(i)];
        if(tmp!=1)ans=min(ans,tmp);
    }
    printf("%d",ans);
    return 0;
}

我用的是类似拓补排序的方法将没有在环中的结点删除
然后再求每个环的大小

#include<stdio.h>
#include<string.h>
int n,t[200010],d[200010]; //t[i]保存输入数据(即传递目标),d保存入度(即被多少人作为传递目标) 
int main(){
    scanf("%d",&n);
    int i,k,c,temp,ans=999999;
    memset(d,0,sizeof(d));
    for (i=1;i<=n;i++){
        scanf("%d",&t[i]);
        d[t[i]]++;  //输入数据,然后子结点入度+1 
    }
    for(i=1;i<=n;i++){  //删除所有不在环中的点(从入度为0的点开始删,删了之后判断其子结点是否入度为0,是就继续删除) 
        if(t[i]==0) continue; //t[i]=0就是这个结点已经被删除了 
        k=i;
        while(d[k]==0){//入度为0就删除 
            temp=t[k];
            t[k]=0;
            k=temp;
            d[k]--;//删除之后它的子结点入度-1,然后继续判断直到有环的结点(有环的结点肯定有其他父结点) 
            
        }
    }
    for(i=1;i<=n;i++){//求最小环 
        if(t[i]==0)continue; 
        k=t[i];c=1;t[i]=0;//c来保存当前环的大小,k作为指针一直往子结点走直到回到原点 
        while(k!=i){
            temp=k;k=t[k];t[temp]=0;
            c++;
        }
        if(ans>c) ans=c;
    }
    printf("%d",ans);
    return 0;
}

/*
这道题很明显就是
在一个只有n条有向边的图中，每个结点出度为1，求一个包含节点数最少的环
1.Tarjan算法求所有强连通分量，
然后再求出所有含结点个数不为1的强连通分量的结点个数的最小值
2.先把入度为0的点删除，然后把这个点指向的点的入度-1，
如果入度为0，也删去，这样就只保留有用的点，
那么从任意一个点开始，用vis数组记录是否被访问过，访问到一个新节点就累加计数器，
然后就做出来了.bfs和dfs都可以.
然后可以保证剩下的每个点都在一个有向环中,
同时这个图特殊的建法好像可以保证任意两个环之间没有公共点
3.并查集判断最小环。
输入的每一条信息路径可以看作一条有向边，答案则是所有环中最小环的长度。
用并查集一边合并图，一边检查新增边的两点是否已经在一个root中。
如果为真，则增加此边后就会成环。此时环的大小为dis[x] + dis[y] + 1，
即为所求答案的一个值。
若为假则增加这条边。
维护并查集时引入了一个dis[]数组，记录此节点到根节点的距离（途径边数），
初始化都为0（自己到自己，不存在边）。
若根节点被并入成为另一个子图的儿子，它的子节点的dis在Find的时候被更新。
若成功新并入一条边，新边出发点的dis在Union的时候被更新。
/*
/*
做法1：Tarjan算法
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <stack>
using namespace std;

const int Maxn =200005;
struct node
{
    int low,index;
    node(int low=-1,int index=-1):low(low),index(index){}
}a[Maxn];
int v[Maxn];
int n;
int Next[Maxn];
int sccnum[Maxn];
int cnt,ans=0x7ffff;
int scc_cnt;
stack<int> s;

void Tarjan(int x)
{
    a[x].index=a[x].low=++cnt;
    s.push(x);
    v[x]=1;
    if(v[Next[x]])
        a[x].low=min(a[x].low,a[Next[x]].index);
    else    if(!sccnum[Next[x]])
    {
        Tarjan(Next[x]);
        a[x].low=min(a[x].low,a[Next[x]].low);
    }
    if(a[x].low==a[x].index)
    {
        int l,tot=0;
        scc_cnt++;
        do
        {
            sccnum[l]=scc_cnt;
            l=s.top();
            tot++;
            s.pop();
        }
        while(l!=x);
        if(tot<=1)  return;
        else ans=min(tot,ans);
    }
}

int main()
{ 
    cin>>n;
    for(int i=1;i<=n;i++)
        cin>>Next[i];
    for(int i=1;i<=n;i++)
        if(!v[i])
            Tarjan(i);
    cout<<ans<<endl;
}
*/  
/*
删掉入度为0的点直接dfs求连通块
注意为了方便这里并没有直接删除结点而是将v[x]标记为1
就可以区分开来
*/
/*
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <queue>
using namespace std;

const int Maxn=200010;
int ans=0x7fffff;
int n;
int to[Maxn];
bool v[Maxn];
int in[Maxn];

void topo(int x)
{
    in[to[x]]--;//邻接点入度-1
    v[x]=1;
    if(!in[to[x]])
        topo(to[x]);
}

void dfs(int x,int tot)
{
    v[x]=1;
    if(!v[to[x]])
        dfs(to[x],tot+1);
    else    if(tot!=1)
        ans=min(ans,tot);
}

int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>to[i];
        in[to[i]]++;
    }
    for(int i=1;i<=n;i++)
        if(!in[i]&&!v[i])
            topo(i);
    for(int i=1;i<=n;i++)
        if(!v[i])
            dfs(i,1);
    cout<<ans<<endl;
    return 0;
}
*/
/*
并查集做法,具体见代码咯，因为是按照边合并的所以肯定不会有独立点的情况
就可以不用特判独立点咯
*/
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;

const int Maxn=200005;
int f[Maxn];
int dis[Maxn];//初始化0
int n;
int ans=0x7fffff;

void init()
{
    for(int i=1;i<=n;i++)
        f[i]=i;
}

int getfather(int x)
{
    if(x==f[x])
        return x;
    int root=f[x];
    f[x]=getfather(f[x]);//这句话要在前面不然WA(先压缩路径？)
    dis[x]+=dis[root];//更改dis路径长度
    return f[x];
}

void Union(int x,int y)
{
    int x1=getfather(x);
    int y1=getfather(y);
    if(x1!=y1)
    {
        f[x1]=y1;//合并集合
        dis[x]=dis[y]+1;//更改长度
    }
    else//找到环了
        ans=min(ans,dis[x]+dis[y]+1);//距离为dis[x]+dis[y]+1
}

int main()
{
    cin>>n;
    init();
    int x;
    for(int i=1;i<=n;i++)
    {
        cin>>x;
        Union(i,x);//合并
    }
    cout<<ans<<endl;
    return 0;
}

乍看是tarjan，再一看每个点出度都是1，所以链的形状是“1”或“6”或“0”，简化成看到有旧时间戳直接返回即可。O(n)解决。

#include <stdio.h>

int next[200001], order[200001] = {0}, chain[200001] = {0}, current_chain = 0;

int visit(int x, int o)
{
    if ((chain[x] > 0) && (chain[x] != current_chain)) return 0;
    chain[x] = current_chain;
    if (order[x]) return o - order[x];
    order[x] = o;
    if (!next[x]) return 0;
    return visit(next[x], o + 1);
}

int main()
{
    int n;
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
        scanf("%d", &next[i]);
    int ans = n;
    for (int i = 1; i <= n; i++)
        if (!chain[i])
        {
            current_chain++;
            int temp = visit(i, 0);
            if ((temp) && (temp < ans)) ans = temp;
        }
    printf("%d", ans);
}

不就是个tarjan嘛......

#include <stdio.h>
#include <algorithm>
#include <stack>
using namespace std;
const int maxn=2e5+5;

int n;
int t[maxn];
int ans=0x7f7f7f7f;
int dfn[maxn],low[maxn],idx;
stack<int>sta;
bool in[maxn];

int cnt[maxn],Bcnt;

void tarjan(int u){
    
    dfn[u]=low[u]=++idx;
    sta.push(u);
    in[u]=1;
    
    int v=t[u];
    if(!dfn[v]) tarjan(v),low[u]=min(low[u],low[v]);
    else if(in[v]) low[u]=min(low[u],dfn[v]);
    
    if(low[u]==dfn[u]){
        
        Bcnt++;
        do{
            v=sta.top();
            sta.pop();
            in[v]=0;
            cnt[Bcnt]++;
        }while(u!=v);
        
    }
}

int main(){
    
    scanf("%d",&n);
    for(int i=1;i<=n;i++) scanf("%d",&t[i]);
    
    for(int i=1;i<=n;i++){
        if(!dfn[i]) tarjan(i);
    }
    
    for(int i=1;i<=Bcnt;i++)
        if(cnt[i]!=1) ans=min(ans,cnt[i]);
    printf("%d",ans);
    return 0;
    
}

稍微优化了一下， 目前应该是比较快的算法时间复杂度应该能到O(n)

#include <cstdio>
#include <cctype>

const int MAXN = 200010, INF = 0x7fffffff;

int n, p, t, x(INF), a[MAXN], f[MAXN], v[MAXN];

//读入优化
inline int ReadInt() {
  char _c; register int sum(0);
  while (!isdigit(_c = getchar()));
  do sum = sum * 10 + _c - '0';
  while (isdigit(_c = getchar()));
  return sum;
}

//输出优化
inline void PutInt(int x) {
  char num[10]; int top(0);
  while (x) num[++top] = x % 10 + '0', x /= 10;
  do putchar(num[top]); while (--top);
  putchar('\n'); return;
}

int main() {
  n = ReadInt();
    //循环展开
  for (register int i = 1; i < n; i += 2)
    a[i] = ReadInt(), a[i + 1] = ReadInt();
  (n & 1) && (a[n] = ReadInt());
  for (register int i = 1; i <= n; ++i) {
    v[i] = 1, t = i, p = a[i];
    while (f[p] - i) {
      if (f[p] && f[p] < i) break;
      v[p] = v[t] + 1, f[t] = i, t = p, p = a[t];
    }
    (!(f[p] - i) && (x > v[t] + 1 - v[p])) && (x = v[t] + 1 - v[p]);
  } PutInt(x);
  return 0;
}

uses
    math;

const
    inf = 200000;

var
    f, d: array[1..200000] of longint; // father, distance
    n, i, j, ans: longint;

function fa(x: longint): longint; // find father
var
    temp: longint;
begin
    if f[x]<>x then
    begin
        temp:= f[x];
        f[x]:= fa(temp);
        d[x]:= d[x] + d[temp];
    end;
    exit(f[x]);
end;

procedure un(x, y: longint); // union
var
    p, q: longint;
begin
    p:= fa(x); q:= fa(y);
    f[p]:= q;
    d[x]:= d[y] + 1;
end;

procedure li(x, y: longint); // link
var
    p, q: longint;
begin
    p:= fa(x); q:=fa(y);
    if p=q then
        ans:= min(ans, d[x] + d[y] + 1)
    else
        un(x, y);
end;

begin // main
    read(n);
    for i:= 1 to n do
    begin
        f[i]:= i;
        d[i]:= 0;
    end;
    ans:= inf;
    for i:= 1 to n do
    begin
        read(j);
        li(i, j);
    end;
    write(ans);
end.

双DFS求强连通分量
var
n,i,j,m,p:longint;
t:array[1..200000]of boolean;
s,q:array[1..200000]of longint;
procedure dfs(x:longint);
begin
t[x]:=false;
if t[s[x]] then dfs(s[x]);
inc(p);
q[p]:=x;
end;
begin
readln(n);
for i:=1 to n do
read(s[i]);
p:=0;
fillchar(t,sizeof(t),255);
for i:=1 to n do
if t[i] then dfs(i);
m:=200000;
fillchar(t,sizeof(t),255);
for i:=1 to n do
if t[q[i]] then
begin
p:=1;
j:=q[i];
t[j]:=false;
while t[s[j]] do
begin
inc(p);
j:=s[j];
t[j]:=false;
end;
if (p>1)and(p<m) then m:=p;
end;
write(m);
end.

70分代码
纯粹模拟
以样例2 4 2 3 1为例
当2在第三轮得知自己的生日时
第二轮的1和3必然知道2的生日
以此逆推
由一到n依次dfs下去
寻找最先出现自己的轮数
再在1到n中寻找最小的那一个值
注意：以5为例；没人告诉过五 所以五永远不知自己的生日
此时5的最小轮数为0
比较时要先判断不为零。
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <vector>
#include <queue>
#define N 10000000+100
using namespace std;
int n,to[N],num[N],t,step,path,ans=N,fg;
vector<int>q[20001];
void dfs(int x)
{
if(x==fg&&step!=0){path=step;return;}
//if(q[x].size()==0)path=N;
for(int i=0;i<q[x].size();i++)
{
step++;
dfs(q[x][i]);
step--;
}
}
int main()
{
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>to[i];
q[to[i]].push_back(i);
}
for(int i=1;i<=n;i++)
{
path=0;
step=0;
fg=i;
dfs(i);
num[i]=path;
}//for(int i=1;i<=n;i++)cout<<num[i]<<endl;
for(int i=1;i<=n;i++)
{
if(num[i]!=0)
ans=min(ans,num[i]);
}
cout<<ans;
return 0;
}

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
using namespace std;
int ok,fa[200001],n,i,j,a[200001],c,x,k,m,used[200001],ans1=100860,ans;
int search(int n)
{
if(n!=fa[n])
return search(fa[n]);
else
return n;
}
int dfs(int n)
{
if(used[n]==1)
return ans;
if(n!=a[n]&&used[n]==0)
{
ans++;
used[n]=1;
dfs(a[n]);
}

}
int main()
{
//freopen("message.in","r",stdin);
//freopen("message.out","w",stdout);
cin>>n;
for(i=1;i<=n;i++)
fa[i]=i;
for(i=1;i<=n;i++)
cin>>a[i];
for(i=1;i<=n;i++)
{
int s1=search(i);
int s2=search(a[i]);
if(s1!=s2)
fa[s1]=s2;
}
for(i=1;i<=n;i++)
if(fa[i]==i)
{
ans=0;
ans1=min(ans1,dfs(i));
}
cout<<ans1;
//fclose(stdin);
//fclose(stdout);
return 0;
}

#include <iostream>
#include <iomanip>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <cctype>
#include <vector>
#include <queue>
using namespace std;
int a[200001],b[200001];
int main()
{
    int n,ans=2147483647,t=0,s,j;
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
    }
    for(int i=1;i<=n;i++)
    {
        if(!b[i])
        {
            t++;
            s=t;
            for(j=i;!b[j];j=a[j])
            {
                t++;
                b[j]=t;
            }
            if(b[j]>=s)
            {
                ans=min(ans,t-b[j]+1);
            }
        }
    }
    printf("%d",ans);
    return 0;
}

tarjan缩点,注意判断是否大小为1。

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cmath>
#define LL long long
using namespace std;
template <class _T> inline void read(_T &_x){
    int _t;bool _flag=0;
    while((_t=getchar())!='-'&&(_t<'0'||_t>'9'));
    if(_t=='-')_flag=1,_t=getchar();_x=_t-'0';
    while((_t=getchar())>='0'&&_t<='9')_x=_x*10+_t-'0';
    if(_flag)_x=-_x;
}
const int maxn=2e5+5;
int n,cnt,x,top,idx,num[maxn],S[maxn],f[maxn],low[maxn],dfn[maxn],head[maxn],ans=0x3f3f3f3f;
bool ins[maxn];
struct edge{
    int v,nxt;
}d[maxn];
inline void add(int a,int b){
    d[++cnt].v=b;d[cnt].nxt=head[a];head[a]=cnt;
}
int find(int x){
    return x==f[x]? x:f[x]=find(f[x]);
}
void tj(int u){
    int v;
    dfn[u]=low[u]=++idx;
    S[++top]=u;ins[u]=1;
    for(int i=head[u];i;i=d[i].nxt){
        v=d[i].v;
        if(!dfn[v]){
            tj(v);
            low[u]=min(low[v],low[u]);
        }
        else if(ins[v])low[u]=min(dfn[v],low[u]);
    }
    if(dfn[u]==low[u]){
        while(u!=v){
            v=S[top--];
            ins[v]=0;
            int f1=find(u),f2=find(v);
            f[f2]=f1;
            if(f1!=f2)num[f1]+=num[f2];
        }
    }
}
int main(){
    read(n);
    for(int i=1;i<=n;i++){
        read(x);
        add(i,x);
    }
    for(int i=1;i<=n;i++)f[i]=i,num[i]=1;
    for(int i=1;i<=n;i++)if(!dfn[i])tj(i);
    for(int i=1;i<=n;i++){
        int tmp=num[find(i)];
        if(tmp!=1)ans=min(ans,tmp);
    }
    printf("%d",ans);
    return 0;
}

我是wys，
发一波题解（tarjan）

#include<cstdio>
#include<stack>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=200005;
const int INF=0x3f3f3f3f;
int n;
int cnt=0,num=0;
int a[maxn];
int dfn[maxn],low[maxn],belong[maxn];
int sq[maxn];//每个强连通分量所含边数  强连通分量中 边数==点数； 
bool instack[maxn];
stack<int > S;
void tarjan(int u){//tarjan
    dfn[u]=low[u]=++cnt;
    S.push(u);
    instack[u]=true;
    int v=a[u];
    if(!dfn[v]){
        tarjan(v);
        low[u]=min(low[u],low[v]);
    }else if(instack[v])
        low[u]=min(low[u],dfn[v]);
    if(dfn[u]==low[u]){
        num++;
        do{
            v=S.top();
            S.pop();
            belong[v]=num;
            sq[num]++;//处理边数 
        }while(dfn[v]!=low[v]);
    }
    return ;
}
int main(){
    int ans=INF;
    scanf("%d",&n);
    for(int i=1;i<=n;i++)scanf("%d",&a[i]);
    for(int i=1;i<=n;i++){//由于图可分为几个强连通分量，所以不做冗余操作； 
        if(!dfn[i])
            tarjan(i);//tarjan处理强连通分量； 
    }
    for(int i=1;i<=num;i++){//找最小环边数； 
        if(sq[i]!=1)ans=min(ans,sq[i]);
    }
    printf("%d\n",ans);
}

http://www.gensokyo.red/?p=505

//一言不合上tarjan

#include<bits/stdc++.h>
#define ll long long
using namespace std;

inline ll read()
{
ll x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}

vector<int>e[200010];
int ind=0,scc=0;
int num[200010],low[200010],dfn[200010],belong[200010];
bool exist[200010],vis[200010];
stack<int>sta;
int ans=1000000007;
int n;

void tarjan(int x)
{
vis[x]=exist[x]=true;
low[x]=dfn[x]=++ind;
sta.push(x);
for(int i=0;i<e[x].size();i++)
{
int p=e[x][i];
if(!vis[p])
{
tarjan(p);
low[x]=min(low[x],low[p]);
}
else
{
if(exist[p])low[x]=min(low[x],dfn[p]);
}
}
int now;
if(low[x]==dfn[x])
{
scc++;
while(now!=x)
{
now=sta.top();
sta.pop();
exist[now]=false;
belong[now]=scc;
num[scc]++;
}
}
}

int main()
{
n=read();
for(int i=1;i<=n;i++)
{
int u=read();
e[i].push_back(u);
}
for(int i=1;i<=n;i++)
if(!vis[i])tarjan(i);
for(int i=1;i<=scc;i++)
if(num[i]>1)
ans=min(num[i],ans);
printf("%d",ans);
return 0;
}

拓扑排序把不在环里的点去掉，然后对在环里的点dfs(dfs时打标记避免重复dfs已经搜过的环内的点，否则会TLE的)

#include<cstdio>
#include<iostream>
#include<algorithm>


using namespace std;

const int MAXN = 200005;
int n, t, ind[MAXN], ans = 0x7fffffff, q[MAXN<<1], hd, tl;
bool circle[MAXN];

struct Edge{
    int nxt, to;
}edge[MAXN];

int head[MAXN], edge_num;
void add_edge(int from, int to){
    edge[++edge_num].nxt = head[from];
    edge[edge_num].to = to;
    head[from] = edge_num;
    ind[to]++;
}

void toposort(){
    for(int i = 1; i <= n; i++)
        if(ind[i] == 0)
            q[tl++] = i;
    while(hd <= tl){
        int cur = q[hd];
        for(int i = head[cur]; i; i = edge[i].nxt){
            ind[edge[i].to]--;
            if(ind[edge[i].to] == 0)
                q[tl++] = edge[i].to;
        }
        hd++;
    }
}

void dfs(int x, int source, int res){
    circle[x] = 1;
    if(x == source && res != 0){
        ans = min(ans, res);
        return;
    }
    for(int i = head[x]; i; i = edge[i].nxt)
        dfs(edge[i].to, source, res+1);
}

int main(){
    scanf("%d", &n);
    for(int i = 1; i <= n; i++){
        scanf("%d", &t);
        add_edge(i, t);
    }
    toposort();
    for(int i = 0; i < tl; i++)
        circle[q[i]] = 1;
    for(int i = 1; i <= n; i++){
        if(!circle[i]){
            dfs(i, i, 0);
        }
    }
    printf("%d", ans);
    return 0;
}

include <cstdio>

using namespace std;

define N 200010

int main()
{
int n=0,m=0; //人数，多少轮
int a[N]={0},birthday[N][N]={0},hi[N][N]={0};
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%d",&a[i]);
hi[i][1]=i;
}

// -----------------------------------------

for(int b=1;b<=n;b++)
{
m++;
for(int i=1;i<=n;i++)
{
int p=a[i];
for(int j=1;j<=n;j++)
{

birthday[p][j]=hi[i][j];
if(hi[i][j]==p)
{
printf("%d",m);
return 0;
}
if(hi[i][j]==0)
{
break;
}
}
}
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
hi[i][j]=0;
}
}
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
hi[i][j]=birthday[i][j];
if(birthday[i][j]==0)
{
break;
}
}
}

}
return 0;
}

就我一个人用了Tarjan吗？

#include<iostream>
#include<cstring>
#include<stack>
using namespace std;
int n;
int a[200001],dfn[200001],low[200001],index=0,ltfl=0,p[200001],minn=2000000;
bool instack[200001];
stack<int> s;
void tarjan(int i){
    dfn[i]=low[i]=++index;
    instack[i]=true;
    s.push(i);
    int j=a[i];
    if(!dfn[j]){
        tarjan(j);
        if(low[i]>low[j])low[i]=low[j];
    }else
    if(instack[j]&&low[i]>dfn[j])low[i]=dfn[j];
    if(low[i]==dfn[i]){
        ltfl++;
        int t=0;
        do{
            t++;
            j=s.top();
            s.pop();
            p[j]=ltfl;
        }while(j!=i);
        if(t>1&&t<minn)minn=t;
    }
}
int main(){
    ios::sync_with_stdio(false);
    cin>>n;
    for(int i=1;i<=n;i++)
    cin>>a[i];
    memset(instack,0,sizeof(instack));
    memset(dfn,0,sizeof dfn);
    memset(low,0,sizeof low);
    for(int i=1;i<=n;i++)
    if(!dfn[i]){
        tarjan(i);
    }
    cout<<minn<<endl;
    return 0;
}