先并查集搜索有无环,然后把环内的点搜索一遍确定最短环
#include <iostream>
#include <cmath>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
int n, x;
queue<int> q;
int way[200001], fa[200001];
int f[200001];
int find(int x) {
if(fa[x] != x)
return fa[x] = find(fa[x]);
return x;
}
int work() {
int top = q.front(), x = q.front();
q.pop();
f[top] = 0;
x = way[x];
f[x] = 1;
while(x != top) {
int k = x;
x = way[x];
f[x] = f[k] + 1;
}
return f[top];
}
int main() {
cin >> n;
for(int i = 1; i <= n; i++)
cin >> way[i], fa[i] = i;
for(int i = 1; i <= n; i++) {
int uu = find(way[i]);
if(uu == i)
q.push(i);
else fa[i] = uu;
}
int min1 = 2147483647;
while(!q.empty()) {
if(f[q.front()] != 0)
q.pop();
else min1 = min(work(), min1);
}
cout << min1 << endl;
return 0;
}

直接暴力标记秒切
什么tarjan一边去
var
i,j,k,o,p,n,m,x,y,ans:longint;
a,b,c,d:array[0..1000000]of longint;
begin
ans:=maxlongint;
readln(n);
for i:=1 to n do read(a[i]);
for i:=1 to n do
begin
if c[i]>0 then continue;
x:=i;
y:=1;
while true do
begin
if c[x]>0 then
begin
if (c[x]=i)and(y-b[x]<ans) then ans:=y-b[x];
break;
end;
b[x]:=y;
c[x]:=i;
x:=a[x];
inc(y);
end;
end;
writeln(ans);
end.

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;

const int maxn = 200000 + 100;
int n;
int ans = 99999999;
int m;
int tot;
struct mem {
    int to;
    int vis1;
    int vis2;
    int d;
} s[maxn];

void dfs (int r, int cnt) {
    if (s[r].vis2 == m) {
        ans = min (ans, tot - s[r].d);
    } 
    else if (s[r].vis1) return;
    else {
        s[r].vis1 = 1;
        s[r].vis2 = m;
        s[r].d = tot;
        dfs (s[r].to, tot++);
    }
}

int main ()
{
    //freopen ("in.txt", "r", stdin);
    cin >> n;
    for (int i = 1; i <= n; i++) scanf ("%d", &s[i].to);
    for (m = 1; m <= n; m++) {
        if (!s[m].vis1) {
            dfs (m, tot++);
        }
    }
    cout << ans;
    return 0;
}

#include <cstdio>
#include <algorithm>
#include <cstring>
#define INF 0x3f3f3f3f
#define N 200005
using namespace std;
int n,ans,t,a[N],ti[N],vis2[N];
bool vis1[N];
void dfs(int k,int cnt){
    if (vis2[k]==t){
        ans=min(ans,cnt-ti[k]);
        return;
    }else{
        if (vis1[k]) return; 
            else{
                vis1[k]=1;
                vis2[k]=t;
                ti[k]=cnt;
                dfs(a[k],cnt+1);
            }
    }
}
int main(){
    scanf("%d",&n);
    ans=INF;
    for (int i=1;i<=n;i++) scanf("%d",&a[i]);
    for (int i=1;i<=n;i++){
        if (!vis1[i]){
            t++;
            dfs(i,1);
        }
    }
    printf("%d\n",ans);
    return 0;
}

并不清楚考试的时候随便打的竟然可以100分-.-
var a,fin,fout,f,q:array[1..200001] of longint;
n,i,j,k,min,l:longint;
team:array[1..500000] of longint;
s:array[1..200000] of boolean;
procedure main;
var i,j,m:longint;
ok:boolean;
begin
m:=1;
for j:=1 to n do begin
if (fin[j]>0) then begin
dec(fin[j]);
i:=j;ok:=false;
end else continue;
while fout[i]<>0 do begin
inc(k);
team[k]:=i;
dec(fout[i]);
dec(fin[a[i]]);
i:=a[i];
ok:=true;
end;
if ok then begin
inc(k);
team[k]:=i;
q[m]:=k;
inc(m);
inc(k);
team[k]:=0;
end;
end;
end;

begin

readln(n);
min:=maxlongint;
for i:=1 to n do begin
read(a[i]);
inc(fin[a[i]]);
inc(fout[i]);
end;
main;
l:=1;
for i:=1 to k do begin
if team[i]=0 then begin inc(l);continue;end;
if team[q[l]]=team[i] then
if (q[l]-i<min)and(q[l]<>i) then min:=q[l]-i;
end;
writeln(min);

end.

并查集优化代码
var
father,road:array[1..1000000]of longint;
a:array[1..1000000] of longint;
flag:array[1..1000000]of boolean;
i,j,k,ans,p,now,n:longint;
function getfather(x:longint):longint;
begin
if father[x]=x then exit(x);
father[x]:=getfather(father[x]);
exit(father[x]);
end;
procedure merge(x,y:longint);
var xx,yy:longint;
begin
xx:=getfather(x);
yy:=getfather(y);
father[xx]:=yy;
end;
function judge(x,y:longint):boolean;
var xx,yy:longint;
begin
xx:=getfather(x);
yy:=getfather(y);
exit(xx=yy);
end;
procedure findround(k:longint);
begin
//road[k]:=1;
now:=0;
p:=k;
while not flag[p] do
begin
flag[p]:=true;
inc(now);
road[p]:=now;
p:=a[p];
end;
if (ans>now-road[p]+1) then
ans:=now-road[p]+1;
end;
begin
readln(n);
fillchar(flag,sizeof(flag),0);
for i:=1 to n do father[i]:=i;
for i:=1 to n do
begin
read(a[i]);
if not judge(i,a[i]) then
merge(a[i],i);
end;
readln;
ans:=maxlongint shr 1;
for i:=1 to n do
if father[i]=i then
findround(i);
writeln(ans);
end.

var
msg,stp:array[1..200000] of longint;
flag,p:array[1..200000] of boolean;
i,j,k,n,tmp,val:longint;
hr:boolean;
begin
assign(input,'message.in'); reset(input);
assign(output,'message.out'); rewrite(output);
readln(n);
val:=maxlongint;
for i:=1 to n do read(msg[i]);
fillchar(p,sizeof(p),false);
for i:=1 to n do
begin
if p[i] then continue;
j:=i;
fillchar(flag,sizeof(flag),false);
k:=0;
hr:=true;
while not flag[j] do
begin
if p[j] then
begin
hr:=false;
break;
end;
flag[j]:=true;
p[j]:=true;
inc(k);
stp[j]:=k;
j:=msg[j];
end;

if hr then
begin
tmp:=k-stp[j]+1;
if tmp<val then val:=tmp;
end;
end;
writeln(val);
close(input);
close(output);
end.

我发一个容易看懂的题解吧
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
bool v[200100];
int a[200100],n,m,ru[200100],k,ans=1,minn=9999999;
void search(int x,int y)
{
int p,t;
if(x==y) return;
if(!v[y]) v[y]=true;
if(!v[x]) {
v[x]=true;
ans++;
search(a[x],y);
}
}
int main()
{
int i,j;
memset(v,false,sizeof(v));

scanf("%d",&n);
for(i=1;i<=n;i++)
{
scanf("%d",&a[i]);
ru[a[i]]++;
}
while(1)
{ k=1;
for(i=1;i<=n;i++)
if(ru[i]==0&&!v[i])
{
k=0;
v[i]=true;
ru[a[i]]--;
}
if(k==1) break;
}

for(i=1;i<=n;i++)
if(!v[i]) {
search(a[i],i);
if(minn>ans) minn=ans;
ans=1;
}

printf("%d",minn);

return 0;
}

求最小环，从每一点尝试dfs，如果在本次dfs中发现再次访问了在本次被访问过的节点，那么说明存在一个环，环的长度就是这个节点被两次访问时的迭代次数之差。只要一次被dfs后就不再访问这个节点，由于每个点只被访问一次，这样的时间效率就是O(n)，轻松AC。

#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;
long ans,ansn;
long road[200001];
bool f[200001];
long p[200001];
long t[200001];
void dfs(long x,long s,long ct)
{
if (!f[x]){
f[x]=true; t[x]=s; p[x]=ct; dfs(road[x],s+1,ct);
} else{
if (s-t[x]<ans && ct==p[x]) ans=s-t[x];
}
}
int main()
{
long n,i;
cin>>n;
for (i=1;i<=n;i++)
scanf("%ld",&road[i]);
memset(f,false,sizeof(f));
ans=n;
for (i=1;i<=n;i++)
if (!f[i])dfs(i,0,i);
printf("%ld",ans);
return 0;
}

Floyd判圈算法+vis数组标记小优化
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
const int MAXN = 2e5 + 5;
bool vis[MAXN];
int t[MAXN];
int n, ans = MAXN;
void Floyd(int i) {
vis[i] = 1;
if (vis[t[i]]) return;
int cur1 = i, cur2 = i;
int cnt = 0;
do {
cur1 = t[cur1];
vis[cur1] = 1;
cur2 = t[t[cur2]];
} while (cur1 != cur2);
do {
cur1 = t[cur1];
++cnt;
cur2 = t[t[cur2]];
} while (cur1 != cur2);
ans = min(ans, cnt);

}
int main() {
memset(vis, 0, sizeof(vis));
scanf("%d", &n);
for (int i = 1; i <= n; ++i) scanf("%d", &t[i]);
for (int i = 1; i <= n; ++i) if (!vis[i]) Floyd(i);
printf("%d\n", ans);
return 0;
}

真的只要剪一下枝就好了啊......
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<cstring>
using namespace std;

int n;
int minn=10000000;

int t[200000+5]={0};
int s[200000+5]={0};
int can[200000+5]={0};
int c[200000+5]={0};

int tt=-1;

inline int min(int a,int b)
{
if(a<b)return a;
return b;

}

void dfs(int now,int step)
{
if(can[now]==tt)
{
minn=min(minn,step-s[now]);
return ;

}
can[now]=tt;
s[now]=step;
dfs(t[now],step+1);

}

int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%d",&t[i]);
c[t[i]]++;
}

for(int i=1;i<=n;i++)
{
if(can[i]==0)
{
if(c[i]!=0)
{
s[i]=1;
dfs(i,1);
tt--;
}
else c[t[i]]--;
}
}
printf("%d",minn);

//while(1);

return 0;

}

求最小环，反正从一个点出只有一个环，去掉入度为0的点然后DFS就好了。为什么我TM考试写得bellmon-ford！！！然后就爆炸了
ps：windows环境会爆栈，然后最后一个点RE，linux是没问题的可以AC，懒得写人工栈。。。
#include<cstdio>
#include<iostream>
#include<cstring>
#define maxn 200010
bool vis[maxn];
int t[maxn],count[maxn];
int ans(1<<29),tar(99999);
int dfs(int s)
{
if(!vis[s])
{
vis[s]=true;
int x=dfs(t[s]);
if(x!=1<<25 && s!=tar)
return x+1;
else if(s==tar) {
ans=std::min(ans,x);
return 1<<25;
}
vis[s]=false;
}
else {
tar=s;
return 1;}
return 1<<25;
}
int main()
{
int n;
scanf("%d",&n);
memset(count,0,sizeof(count));
for(int i=1;i<=n;i++)
{
scanf("%d",&t[i]);
count[t[i]]++;
}
memset(vis,0,sizeof(vis));
for(int i=1;i<=n;i++)
if(!vis[i] && count[i]>0)
dfs(i);
printf("%d",ans);
return 0;
}

直接搜索，搜索的同时记录
开数组记录点：没搜过、不在环内、在环内（记录环的长度）
对于一个新的以前没搜过的点x 搜到下列三种情况停止：
1. 搜索到这次循环新遍历到的点y，即出现新的环
2. 之前记录的环上的节点y
3. 之前记录的非环上的点y

对于1： 从x到y之前的点标为环外，对于剩下的点标环的长度
对于2、3： 这次搜到的全标成环外
一直搜到所有点都搜过

最后暴搜所有点
找环内点记录的环的长度的最小值
输出即可
每个点走常数次
O（n）

考试的时候没什么思路，知道是求最小环（画有向图）写了个递推。70%能过

后来写斗地主的时候发现不对劲，这道题可能涉及多个连通块。说到连通块，我想到并查集，于是一发不可收拾找到了时间复杂度n的算法。

因为对于每个连通块来说都一定有出度。因此从一个连通块任意位置出发。第一个点记1，第二个为2，请把样例1的图画起来跟我这样模拟。我们给2号点记为3,4为4,5为5，然后又回到了2.此时应记6，但是2之前已经有记为3了。那么ans：=now-x
now为目前记的值。x为之前的数。也就是说如果X不为0就可以计算ans。然后退出。这就是最小环？为什么？因为我们发现。一个连通块只能有一个环！！

那么这就是n的算法，对每个连通块扫一遍即可。连通块的判断用并查集。对每棵树从根扫描。当然不用并查集也可以的

pascal代码等我比赛程序发回来再发...
###pascal code
program message1;
var n,i,ans,ans2:longint;
t,a,fa:array[1..200000] of longint;
function find(x:longint):longint;
begin
if fa[x]=x then exit(x);
fa[x]:=find(fa[x]); find:=fa[x];
end;

procedure add(x,y:longint);
begin
x:=find(x); y:=find(y);
fa[y]:=x;
end;

procedure search(now,s:longint);
begin
if a[now]<>0 then begin ans:=s-a[now]; if ans<ans2 then ans2:=ans; exit; end;
if a[now]=0 then a[now]:=s;
search(t[now],s+1);
end;
begin
read(n);
for i:=1 to n do fa[i]:=i;
for i:=1 to n do begin read(t[i]); add(i,t[i]); end;
fillchar(a,sizeof(a),0); ans2:=maxlongint;
for i:=1 to n do
if fa[i]=i then
search(i,1);
write(ans2);
end.

是简单的搜索，选择一个数i，不断的访问其后续，并记录步数k，将节点i压入栈中，mark=true。如果要访问的节点mark[ti]==true那么开始弹出栈内元素，如果弹出的元素等于ti那么ans=min(ans,k-k[ti]+1);一个个元素向下走。直到每个元素的mark==true。运算步数最小为2n，最多为3n时间复杂度为O(n) 对于n<=200000的情况可以AC。
别问我为什么第二题的算法像Tarjan，我本来就是在求环（单向的强连通分量），正确性是在于每个节点只有一条路径离开！所以形成的强连通分量一定是一个单向环！
#define _CRT_SECURE_NO_DEPRECATE
#include<iostream>
#include<cstdio>
#include<fstream>
using namespace std;

long n,head,d,step,ans=200006;
long t[200005] = { 0 }, k[200005] = { 0 },s[200005];
bool mark[200005] = { false };

int main()
{
cin >> n;
for (int i = 1; i <= n; i++)
scanf("%ld", &t[i]); //cin的效率好像比较低
for (int i = 1; i <= n; i++)
{
head = 1;
d = i;
step = 0;
mark[d] = true;
k[d] = 0;
s[head] = d;
while (!mark[t[d]])
{
step++;
d = t[d];
head++;
s[head] = d;
k[d] = step;
mark[d] = true;
}
while (head--)
if (s[head] == t[d])
{
ans = ans > k[d] - k[s[head]] + 1 ? k[d] - k[s[head]] + 1 : ans;
break;
}
}
cout << ans;
// system("pause"); 这个是VS编译时候出来的，忽略掉
return 0;
}