传送门
一开始没在意数据范围...就用一个5行的dfs瞎做，搞了80分。
正解是带权并查集，只需要维护一下到根节点的距离就可以了。。。。
#include<bits/stdc++.h> #define N 200005 using namespace std; int n,father[N],to_root[N],ans=0x7ffffff; inline int getfather(int x) { if(father[x]==x) return x; int fa=father[x]; father[x]=getfather(father[x]); to_root[x]+=to_root[fa]; return father[x]; } inline void merge(int x,int y) { int ax=getfather(x); int bx=getfather(y); if(ax!=bx){ father[ax]=bx; to_root[x]=to_root[y]+1; } else ans=min(ans,to_root[x]+to_root[y]+1); } int main() { cin>>n; for(int i=1;i<=n;i++) father[i]=i; for(int i=1;i<=n;i++) { int x; cin>>x; merge(i,x); } cout<<ans<<endl; return 0; }转载于:https://www.cnblogs.com/Patrickpwq/articles/9452272.html
相关资源：各显卡算力对照表！