先看一下一下样例：
Sample Input: 5 2 4 2 3 1 Sample Output: 3可以认为是这样的
1->2 2->4 3->2 4->3 5->1然后我们发现若抽象成图。 图中有一个环(2->4->3->2)，大小正好是3。 可以推知：环内的人必定在环的大小单位时间后得到自己的信息。 所以直接找最小环 But, n<=2∗105 一个个人找环时间复杂度最大为 O(n2) 我们发现： 找一个环，还上每个人都会遍历到。 所以可以并查集排除重复的或记下经过的人。 参考代码：
int n,ans=0x3f3f3f3f,g[200010],f[200010]; int getf(int x) { rt f[x]=(x==f[x]?x:getf(f[x])); } int main(){ n=read(); fr(i,1,n) g[i]=read(); fr(i,1,n) f[i]=i; fr(i,1,n) f[i]=getf(g[i]); fr(i,1,n) if(i==____) { int k=g[i],t=1; while(k!=i) { k=g[k]; t++; } ans=__________; } printf("%d\n",ans); rt 0; }送大家两个空去填
