并查集
P1653
每个猴子掉下取得时候，就是它与1断开连接得时候，所以可以倒着搜，每次用并查集将两个猴子连接上，将每个猴子与1联通得时间记录下来即可。
P2661
对于有向环，可以用并查集求解。
设\(d[a]\)表示节点\(a\)到根节点的距离，那么每次路径压缩时都要更新\(d[a]\).
假设节点\(d[b]=0，d[a]=x\),那么当\(d[b]=y\)时，\(d[a]=x+y\),即\(d[a]+=d[lst]\).不用关心\(a\)的父节点怎样变化，因为已经路径压缩过，所有节点都已经并在一个根节点上，而这个根节点\(d[b]=0\),所以只需要关心它的值的变化量，即\(d[lst]-0=d[lst]\).
因为根据题意，每个节点只有一个父亲，所以不会出现多个父节点导致的混乱，所以可以说\(d[b]=0\).
而判断环的时候，因为不知道那个节点的\(d[ ]=0\),所以返回\(da]+d[b]+1\)即可。
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int N=2e5+10;
int n,minn,k;
int fa[N],d[N];
int getfa(int u){
if(fa[u]!=u){
int lst=fa[u];
fa[u]=getfa(fa[u]);
d[u]+=d[lst];
}
return fa[u];
}
void add(int a,int b){
int x=getfa(a),y=getfa(b);
if(x!=y){
fa[x]=y;d[a]=d[b]+1;
}else minn=min(minn,d[a]+d[b]+1);
}
int main(){
scanf("%d",&n);
minn=0x3f3f3f3f;
for(int i=1;i<=n+1;++i)fa[i]=i;
for(int i=1;i<=n;++i){
scanf("%d",&k);
add(i,k);
}
printf("%d",minn);
return 0;
}