#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int MAXN=200100;
int n,to[MAXN],time[MAXN],ans=2*MAXN,preto[MAXN],vis[MAXN];
void search(int x,int t)
{
    if(time[to[x]]!=0){
        ans=min(ans,t-time[to[x]]+1);
        return;
    }
    else{
        time[x]=t;
        vis[x]=1;
        search(to[x],t+1);
    }
}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++) scanf("%d",&to[i]),preto[to[i]]=i;
    for(int i=1;i<=n;i++){
        if(preto[i]==0) continue;
        if(vis[i]) continue;
        memset(time,0,sizeof(time));
        time[i]=1;
        search(i,1);
    }
    printf("%d",ans);
    return 0;
}

先剪枝，不断剪掉入度为0的点，剩下的点肯定构成环。然后找最大环就行了应该是吧
program message;
var ru,chu:array[1..200000] of longint;
i,n,ans:longint;
procedure jianzhi;
var
dui:array[0..200000] of longint;
tail,head,j:longint;
begin
tail:=0;
head:=1;
for j:=1 to n do
if ru[j]=0 then
begin
inc(tail);
dui[tail]:=j;
dec(ru[chu[j]]);
end;
while head<=tail do
begin
if ru[chu[dui[head]]]<=0 then
begin
inc(tail);
dui[tail]:=chu[dui[head]];
dec(ru[chu[dui[tail]]]);
end;
inc(head);
end;
end;

procedure dfs(x,st,i:longint);
begin

if ru[x]=0 then exit;
ru[x]:=0;
if (x=i)then begin
if st<ans then ans:=st;
exit;
end;
dfs(chu[x],st+1,i);
end;

begin
assign(input,'www.in');
reset(input);
assign(output,'www.out');
rewrite(output);
readln(n);
for i:=1 to n do ru[i]:=0;
for i:=1 to n do
begin
read(chu[i]);
inc(ru[chu[i]]);
end;
jianzhi;

ans:=maxlongint;
for i:=1 to n do
if ru[i]>0 then dfs(chu[i],1,i);
writeln(ans);
close(input);
close(output);
end.

说的什么并查集。。太麻烦
做法：
会有很多入度为0的没用的枝杈，这些是不可能构成环的，所以不需要进行搜索，直接剪枝。
然后 就是简单的图的dfs遍历 首先在主程序里面记录下全局变量st，记录开始搜索的节点编号，记录dfs到这一个点的步数便是从这一个点开始，能构成的环的大小，朴素做法就是都找一遍不断更新ans值。其实感觉可以再有一个剪枝 不过懒得想了= =
```pascal
program mes;
var
t,inn:array [0..200020] of longint;
n,ans,i,j,st,sum:longint;
o:array [0..200020] of boolean;

PROCEDURE dfs(x:longint);
begin
inc(sum);
o[x]:=true;
if (t[x]=st) then exit;
dfs(t[x]);
end;
PROCEDURE del(x:longint);
begin
o[x]:=true;
dec(inn[t[x]]);
if (inn[t[x]] = 0) then del(t[x]);
end;

BEGIN
fillchar(o,sizeof(o),false);
ans:=200000;
readln(n);
for i:=1 to n do
begin
read(t[i]);
inc(inn[t[i]]);
end;
for i:=1 to n do
begin
if (not o[i]) and (inn[i] = 0) then del(i);
end;
for i:=1 to n do
begin
if o[i]=false then
begin
st:=i;
sum:=0;
dfs(i);
if sum<ans then ans:=sum;
end;
end;
writeln(ans);
END.
```

#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <algorithm>
using namespace std;
const int M = 200005;
const int INF = 0x7fffffff;

int f[M], vis[M], done[M], ans = INF;

void dfs(int x, int tep){
int bri = x;
while(1){
vis[x] = tep;
if(vis[f[x]] && !done[f[x]]){
ans = min(ans, tep - vis[f[x]] + 1);
break;
}
if(done[f[x]]) break;
x = f[x], tep++;
}
x = bri;
while(1){
done[x] = 1;
if(done[f[x]]) return;
x = f[x];
}
}

int main()
{
freopen("in", "r", stdin);
int n;
scanf("%d", &n);
for(int i = 1; i <= n; i++) scanf("%d", &f[i]);
for(int i = 1; i <= n; i++)
if(!done[i])
dfs(i, 1);
printf("%d", ans);
return 0;
}
那年，怀恨，一把辛酸泪

Topological sorting + DFS

#include <cstdio>
#include <algorithm>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#include <queue>
#define MAXN 200000 + 10
using namespace std;
int n, m, in[MAXN], to[MAXN], vis[MAXN], minw = MAXN, node;
queue<int> q;
int dfs(int i, int sum) {
vis[i] = 1;
if(!vis[to[i]])
dfs(to[i], sum + 1);
else {
minw = min(minw, sum + 1);
}
}
int main() {
ios::sync_with_stdio(false);
cin >> n;
for (int i = 0; i < n; i++) {
int t;
cin >> t;
t--;
in[t]++;
to[i] = t;
}
for (int i = 0; i < n; i++) {
if (in[i] == 0) {
q.push(i);
vis[i] = 1;
}
}
while(!q.empty()) {
int p = q.front();
q.pop();
in[to[p]]--;
if(!in[to[p]]) {
vis[to[p]] = 1;
q.push(to[p]);
}
}
for (int i = 0; i < n; i++) {
node = 0;
if (!vis[i] && in[i])
dfs(i, 0);
}
cout << minw;
return 0;
}


O（N）
#include <cstdio>

int n,p,sp,ans=99999999,t[210000],vis[210000]={0};

void dfs(int u,int step){
vis[u]=1;
if(!vis[t[u]])
dfs(t[u],step+1);
else
p=t[u],sp=step;
if(u==p)
ans=ans<(sp-step)?ans:(sp-step);

}

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

var
a,b,c:array [0..200005] of longint;
n,t,i,ans,p,s,x:longint;
function min(x,y:longint):longint;
begin if (x<y) then exit(x) else exit(y); end;
begin
readln(n); t:=0; p:=0; ans:=1000000;
for i:=1 to n do read(a[i]);
for i:=1 to n do
if (b[i]=0) then
begin
x:=i; s:=0;
while true do begin if (b[x]<>0) then break; inc(s); b[x]:=1; c[x]:=s; x:=a[x]; end;
if (b[x]=1) and (s-c[x]+1>1) and (s-c[x]+1<ans) then ans:=s-c[x]+1;
x:=i;
while true do begin if (b[x]=2) then break; b[x]:=2; x:=a[x]; end;
end;
writeln(ans);
end.

//HBat
//找环，找过的不用再找。
#include <iostream>
#include <cstdio>
#include <cstring>

using namespace std;

#define MAXN 200001

int minlong=0x7fffff;//最小环
int n;//人数
int nextp[MAXN];//告诉的人
int blot[MAXN];//已经访问过的，并标记地几次访问
int nblot[MAXN];//在一组访问中的第几个人

int main()
{
int i,temp,k,kc;
int ls=0;//标记已经访问的人数，当ls==n就可以结束了
memset(blot,0,sizeof(blot));//初始化
cin>>n;
for(i=1;i<=n;++i)
cin>>nextp[i];
kc=0;//访问组标号
k=1;//查找环开始人
while(ls<n&&k<=n)//ls<n
{
temp=k;//进入查找环
i=0;//在一组访问中的第几个人
++kc;
do
{
i++;//在一组访问的第i个人
if(blot[temp]==0)ls++;//如果从来没有访问过就记录
blot[temp]=kc;//入组
nblot[temp]=i;//组名次
temp=nextp[temp];//下一个
if(blot[temp]==kc)//看是否构成一个环，构成，结束
{
minlong=minlong<(i-nblot[temp]+1)? minlong:(i-nblot[temp]+1);
break;
}
else if(blot[temp]!=0)break;//如果以前的组访问过就不需要再访问了，否则循环
}while(i<=n&&ls<n);//ls<n
if(ls>=n)break;//ls<n
while(k<=n)//搜索下一个查找点
if(blot[++k]!=0)continue;
else break;
}
cout<<minlong;//输出
return 0;
}

可证明环与环无交叉不联通
去掉非环点
然后想怎么搜怎么搜
模拟都能过
var a,num:array[1..200000]of longint;
i,j,n,x,x1,x2,min:longint;
procedure dfs(x:longint);
begin
if num[x]=0 then
begin
dec(num[a[x]]);
dfs(a[x]);
a[x]:=0;
end
else exit;
end;

begin
readln(n);
for i:=1 to n do
begin
read(x);
a[i]:=x;
inc(num[x]);
end;
for i:=1 to n do
if num[i]=0 then dfs(i);
min:=n+1;
for i:=1 to n do
begin
x:=0;
if a[i]>0 then
begin
x1:=i;
while a[x1]>0 do
begin
x2:=x1;
x1:=a[x1];
a[x2]:=0;
inc(x);
end;
if min>x then min:=x;
end;
end;
write(min);
readln;readln;
end.

先去掉一些入度为零的点，再用深度搜索
program lij;
const maxn=200001;
var link,ind,cc:array[0..maxn]of longint;
f1,f2:array[0..maxn]of boolean;
i,n,m,ans,min:longint;
procedure readin;
begin
readln(n);
for i:=1 to n do
begin
read(link[i]);
inc(ind[link[i]]);
end;
for i:=1 to n do
f1[i]:=(ind[i]=0);
end;
procedure dfs(i:longint);
var j:longint;
begin
inc(m);cc[i]:=m;
f1[i]:=true;f2[i]:=true;
j:=link[i];
if f2[j]=false then
begin
if f1[j]=false then
dfs(j)
end
else
begin
ans:=m-cc[j];
if ans<min then
min:=ans;
end;
end;
begin
min:=maxlongint;
fillchar(ind,sizeof(ind),0);
readin;
i:=1;
while true do
begin
while f1[i]=true do
inc(i);
if i<=n then
begin
fillchar(cc,sizeof(cc),0);
fillchar(f2,sizeof(f2),0);
m:=0;
dfs(i);
end
else break;
end;
writeln(min+1);
end.

最后一个点爆栈

先找环，再算长度...
、、、c++
#include<iostream>
#include<cstdio>
using namespace std;
const int N=200010;
int to[N];
int visited[N],k=1;

int main(){
int n,Min=99999999;
scanf("%d",&n);
for(int i=1;i<=n;i++)scanf("%d",&to[i]);
for(int i=1;i<=n;i++){
if(!visited[i]){
int nown=i;
while(!visited[nown]){
visited[nown]=k;
nown=to[nown];
}
if(visited[nown]!=k){
k++; continue;
}
int start=nown,cnt=0;
nown=to[nown];
while(nown!=start)cnt++,nown=to[nown];
cnt++;
if(cnt<Min)Min=cnt;
k++;
}
}
printf("%d",Min);
return 0;
}
、、、

哎，现在的TG怎么这么水QAQwww

#include<iostream>
#include<cstdio>
using namespace std;
int ans=99999999,n,p[200050]={0},t[200050],used[200050],time[200050];
void dfs(int now,int step,int cnt){
    used[now]=1;
    //记录当前步数 
    time[now]=step;
    //注意要标记是否从同一个点出发 
    p[now]=cnt;
    if(!used[t[now]]){
        dfs(t[now],step+1,cnt);
    }
    else{
        if(p[t[now]]==cnt){
            ans=min(time[now]-time[t[now]]+1,ans);//环的长度为两部数差 
        }
    }
}
int main(){
    freopen("in.txt","r",stdin);
    cin>>n;
    int i,step;
    for(i=1;i<=n;i++){
        cin>>t[i];
        used[i]=0;
    }
    for(i=1;i<=n;i++){
        //每个点实际上只需被访问一次 
        if(!used[i]){
            step=1;
            dfs(i,step,i);
        }
    }
    cout<<ans;
    return 0;
}
```

编译器爸爸告诉我不能用next，会有歧义就CE了两次QWQ
并查集+dfs
#include<iostream>
#include<cstring>
#include<cstdio>
#define inf 210000000
#define N 200005
using namespace std;
int n,ans,y;
int f[N],nxt[N],h[N];
bool b[N];
int find(int x){
if(x==f[x]) return x;
f[x]=find(f[x]);
return f[x];
}
void merge(int x,int y){
int f1=find(x);
int f2=find(y);
f[f1]=f2;
return ;
}
void dfs(int x,int dep){
b[x]=true;h[x]=dep;
if(!b[nxt[x]])
dfs(nxt[x],dep+1);
else{
int k=h[x]-h[nxt[x]]+1;
ans=min(ans,k);
}

return ;
}
int main(){
scanf("%d",&n);
ans=inf;
for(int i=1;i<=n;i++)
f[i]=i;
for(int i=1;i<=n;i++){
scanf("%d",&y);
nxt[i]=y;
if(find(i)!=find(y))
merge(i,y);
else{
memset(b,0,sizeof(b));
dfs(i,1);
}
}
printf("%d",ans);
return 0;

}

测试数据 #0: Accepted, time = 0 ms, mem = 3160 KiB, score = 10

测试数据 #1: Accepted, time = 0 ms, mem = 3156 KiB, score = 10

测试数据 #2: Accepted, time = 0 ms, mem = 3160 KiB, score = 10

测试数据 #3: Accepted, time = 0 ms, mem = 3160 KiB, score = 10

测试数据 #4: Accepted, time = 15 ms, mem = 3156 KiB, score = 10

测试数据 #5: Accepted, time = 0 ms, mem = 3156 KiB, score = 10

测试数据 #6: Accepted, time = 31 ms, mem = 3156 KiB, score = 10

测试数据 #7: Accepted, time = 31 ms, mem = 3160 KiB, score = 10

测试数据 #8: Accepted, time = 31 ms, mem = 3156 KiB, score = 10

测试数据 #9: Accepted, time = 62 ms, mem = 3160 KiB, score = 10

Accepted, time = 170 ms, mem = 3160 KiB, score = 100

代码

var
b,t,a:array[1..200000] of longint;
top,min,n,next,pre,x,i,j:longint;
begin
readln(n);
for i:=1 to n do read(t[i]);
for i:=1 to n do b[i]:=0;
top:=0;
min:=999999;
for j:=1 to n do
begin
if (b[j]=0 )and (b[t[j]]=0) then
begin
pre:=j;
b[j]:=1;
top:=top+1;
a[top]:=j;
while b[t[pre]]=0 do
begin
pre:=t[pre];
b[pre]:=1;
top:=top+1;
a[top]:=pre;
end;
top:=top+1;
a[top]:=t[pre];
x:=a[top];
for i:=1 to top do
begin
if a[i]=x then

begin
if (top-i)<min then min:=top-i;
break;
end;
end;
end;
end;
writeln(min);
end.

水题……

评测结果

编译成功

测试数据 #0: Accepted, time = 0 ms, mem = 2316 KiB, score = 10

测试数据 #1: Accepted, time = 0 ms, mem = 2316 KiB, score = 10

测试数据 #2: Accepted, time = 0 ms, mem = 2320 KiB, score = 10

测试数据 #3: Accepted, time = 0 ms, mem = 2324 KiB, score = 10

测试数据 #4: Accepted, time = 15 ms, mem = 2320 KiB, score = 10

测试数据 #5: Accepted, time = 15 ms, mem = 2320 KiB, score = 10

测试数据 #6: Accepted, time = 187 ms, mem = 2800 KiB, score = 10

测试数据 #7: Accepted, time = 203 ms, mem = 2840 KiB, score = 10

测试数据 #8: Accepted, time = 203 ms, mem = 2800 KiB, score = 10

测试数据 #9: Accepted, time = 234 ms, mem = 2748 KiB, score = 10

Accepted, time = 857 ms, mem = 2840 KiB, score = 100

本蒟蒻是酱紫做的……
先拓扑去掉所有的非环上节点……（因为他们不可能从别人口中得知任何人的生日，他们是不可能的），然后留下的环都是简单环……然后递归获取环长，答案就是环长中的最小值。
这个算法不是最优的，但是857MS还是挺快的。
代码如下
c++
#include <iostream>
#include <utility>
#include <queue>
#include <climits>
using namespace std;
int n,ans=INT_MAX;
bool book[200005];
pair<int,int> p[200005];
queue<int> que;
int roundl(int x,int dx,int total)
{
book[x]=1;
if(x==dx)return total+1;return roundl(p[x].first,dx,total+1);
}
int main()
{
ios::sync_with_stdio(0);
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>p[i].first;
p[p[i].first].second++;
}
for(int i=1;i<=n;i++)if(!p[i].second)que.push(i);
while(!que.empty())
{
book[que.front()]=1;
if(!--p[p[que.front()].first].second)que.push(p[que.front()].first);
que.pop();
}
for(int i=1;i<=n;i++)if(!book[i])ans=min(ans,roundl(p[i].first,i,0));
cout<<ans;
return 0;
}


思路：从每个点dfs，标记访问过的点，
如果在搜索中遇到访问过的，回溯，
看能否构成环，若能，则比较环的长度与ans，更新ans

开始打出来，过9个 第十个RE
加个inline就好了
#include <cstdio>

int n,t[200050];
int visited[200050]={0};
int mindist=200088;
int node;

inline int dfs(int i,int dist){
visited[i]=1;
if(!visited[t[i]])
dist=dfs(t[i],dist);
else
node=t[i];
if(node==i)
mindist=mindist<dist?mindist:dist;

return dist+1;
}

int main(){
// freopen("in.txt","r",stdin);
scanf("%d",&n);
for(int i=1;i<=n;i++)
scanf("%d",&t[i]);
for(int i=1;i<=n;i++){
node=0;
if(!visited[i])
dfs(i,0);
}
printf("%d",mindist+1);

return 0;
}

scanf有毒，深刻地体会到cin的慢了

#include<iostream>
#include<cstring>
#define maxn 200005
using namespace std;

int n,u[maxn],minium = 0x7fffffff,time[maxn],now = 1;
//memset(time,0,sizeof(time));
bool been[maxn];
void dfs(int p){
    memset(been,0,sizeof(been));
    while(!time[p]){
        time[p]=now++;
        been[p]=1;
        if(been[u[p]]){
            minium=min(time[p]-time[u[p]]+1,minium);
            break;
        }
        p = u[p];
    }
}

int main(){
    freopen("message.in","r",stdin);
    scanf("%d",&n);
    for(int i = 1;i<=n;i++)scanf("%d",&u[i]);
    for(int i = 1;i<=n;i++){
        if(!time[i])dfs(i);
    }
    printf("%d\n",minium);
    return 0;
}

本题在并查集的基础上增加路径长度的判断。当有向边<x,y>的两个顶点不在同一集合时，利用并查集算法将x，y两个结点合并起来。设cnt[x]代表结点x经过cnt[x]次的合并才能并入结点y所在集合。则cnt[x]:=cnt[y]+1；
program vj1979;
var
father,t,cnt:array[1..200000] of longint;
ans,n,i,j:longint;
function min(a,b:longint):longint; //求两数中的最小值
begin
if a<b then exit(a); exit(b);
end;
function getfather(v:longint):longint; //查找v元素所在集合中的根，cnt[v]表示V结点在该集合中的深度
var tmp:longint;
begin
if father[v]=v then exit(v);
tmp:=father[v];
father[v]:=getfather(father[v]);
cnt[v]:=cnt[v]+cnt[tmp];
exit(father[v]);
end;
function judge(x,y:longint):boolean;
var xx,yy:longint;
begin
xx:=getfather(x);
yy:=getfather(y);
exit(xx=yy);
end;
procedure merge(x,y:longint);//合并集合
var xx,yy:longint;
begin
xx:=getfather(x);
yy:=getfather(y);
father[xx]:=yy;
cnt[x]:=cnt[y]+1;
end;
begin
readln(n);
for i:=1 to n do begin father[i]:=i; cnt[i]:=0; end;
ans:=maxlongint;
for i:=1 to n do begin
read(t[i]);
if not judge(i,t[i]) then merge(i,t[i]) else ans:=min(ans,cnt[i]+cnt[t[i]]+1);
end;

writeln(ans);
end.