首先,我们知道每个人只能告诉一个人(一个出度),却能被几个人告知(入度不定)。
结论1:入度为0的人不可能从他人那里知道自己生日;
结论2:假如入度为1的人的那个“1”入度为0,那么他也不可能从他人那里知道自己生日。
所以我们先把所有入度为0的人排除,以及让被排除的人的告诉的人的入度减一,直到没有入度为0的人;
又因为每个人只有一个出度,那么剩下的人的告知关系一定会变成几个环;然后就只统计每个环就行了,但是数据大了这种方法还是会超时。
#include<bits/stdc++.h>
using namespace std;
int m=9999999,n;
int ha[200010],kao[200010];
int sf(int st,int hahaha){
kao[st]=0;
if(st==kao[0]) return hahaha;
else return sf(ha[st],hahaha+1);
}
int main(){
// freopen("message.in","r",stdin);
// freopen("message.out","w",stdout);
int q[200010]={0},w[200010];
scanf("%d",&n);
for(int z=1;z<=n;++z){
scanf("%d",&ha[z]);
++kao[ha[z]];
}
for(int z=1;z<=n;++z)
if(!kao[z])
q[++q[0]]=z;
kao[0]=1;
while(1){
if(kao[0]&1){
w[0]=0;
for(int z=1;z<=q[0];++z){
--kao[ha[q[z]]];
if(!kao[ha[q[z]]]){
kao[0]=2;
w[++w[0]]=ha[q[z]];
}
}
if(!w[0]) break;
}
else{
q[0]=0;
for(int z=1;z<=w[0];++z){
--kao[ha[w[z]]];
if(!kao[ha[w[z]]]){
kao[0]=1;
q[++q[0]]=ha[w[z]];
}
}
if(!q[0]) break;
}
}
for(int z=1;z<=n;++z)
if(kao[z]){
kao[0]=z;
m=min(m,sf(ha[z],1));
}
printf("%d",m);
}