今天在题库发现了一个wa了很久还没调过的题，这个题呢是2015年noip的day1t2，莫名感觉难度上升（其实水的一匹）。
这道题输出是3，其实就是一个图中让你找最小环，尽管我不会找环，但是要是我的话应该也是可以水过部分分的，尧神说这道题咋打都能过，但我不会啊，于是开始了模拟，开了两个动态的数组进行模拟这个过程，一个传个另一个（很傻的做法）但我还是打了，代码量100+，于是轻轻松松过了样例点了提交不知道能过多少，嗯，20分，还行，后面dalao说这道题简单的很，交给我并茶几判环，不会啊，代码量就顶多50+，过了，然后一直看他的代码，记忆性的打出了他的代码理解不了最后在洛谷上找了篇题解，才发现自己没真正理解题目，画了个图知道了真正的找最小环，topsort完以后剩下的就剩环了dfs寻找最小的就行了，也还算简单，深刻理解环。
代码：
#include<iostream> #include<cstring> #include<string> #include<cmath> #include<ctime> #include<cstdio> #include<iomanip> #include<algorithm> #include<vector> #include<stack> #include<queue> #include<map> using namespace std; inline int read() { int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } const int maxn=200003; int a[maxn],d[maxn],b[maxn],ans=1e8; int n; void delet(int x) { d[x]=-1; b[a[x]]--; if(b[a[x]]==0&&d[a[x]]!=-1) delet(a[x]); } void dfs(int r,int l,int num) { if(l==r&&num!=0) { ans=min(ans,num); return; } if(d[a[r]]==0) { d[a[r]]=1; dfs(a[r],l,num+1); } } int main() { //freopen("1.in","r",stdin); n=read(); memset(d,0,sizeof(d)); memset(b,0,sizeof(b)); memset(a,0,sizeof(a)); for(int i=1;i<=n;i++) a[i]=read(),b[a[i]]++; for(int i=1;i<=n;i++) { if(b[i]==0&&d[i]!=-1) { delet(i); } } for(int i=1;i<=n;i++) { if(d[i]==0) dfs(i,i,0); } printf("%d ",ans); return 0; }
闻道玉门犹被遮，应将性命逐轻车。