拓扑_dfs——找最小环

今天在题库发现了一个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=,f=;char ch=getchar();

    while(ch<''||ch>''){if(ch=='-')f=-;ch=getchar();}

    while(ch>=''&&ch<=''){x=x*+ch-'';ch=getchar();}

    return x*f;

}

const int maxn=;

int a[maxn],d[maxn],b[maxn],ans=1e8;

int n;

void delet(int x)

{

    d[x]=-;

    b[a[x]]--;

    if(b[a[x]]==&&d[a[x]]!=-)

        delet(a[x]);

}

void dfs(int r,int l,int num)

{

    if(l==r&&num!=)

    {

        ans=min(ans,num);

        return;

    }

    if(d[a[r]]==)

    {

        d[a[r]]=;

        dfs(a[r],l,num+);

    }

}

int main()

{

    //freopen("1.in","r",stdin);

    n=read();

    memset(d,,sizeof(d));

    memset(b,,sizeof(b));

    memset(a,,sizeof(a));

    for(int i=;i<=n;i++)

        a[i]=read(),b[a[i]]++;

    for(int i=;i<=n;i++)

    {

        if(b[i]==&&d[i]!=-)

        {

            delet(i);

        }

    }

    for(int i=;i<=n;i++)

    {

        if(d[i]==)

        dfs(i,i,);

    }

    printf("%d\n",ans);

    return ;

}

闻道玉门犹被遮，应将性命逐轻车。