一道特别好的深搜题+bfs

P2921 [USACO08DEC]Trick or Treat on the Farm G

深搜的技巧全用到了，写这个题解的人深搜也太好了吧 https://www.luogu.com.cn/problem/P2921

（改天加注释复习）

#include 

using namespace std;
const int maxn=1e6+5;
const int inf=0x3f3f3f3f;
int nxt[maxn],n,cnt,f[maxn],h[maxn],fg;
bool vis[maxn];

int dfs(int u,int k)
{
    if(h[u])
        return h[u]-1+k;
    if(vis[u])
    {
        h[u]=k-f[u];
        fg=u;
        return k-1;
    }
    vis[u]=1;
    f[u]=k;
    int ans=dfs(nxt[u],k+1);
    if(fg)
    {
        if(u==fg)
            fg=0;
        else
            h[u]=h[fg];
    }
    else
        h[u]=h[nxt[u]]+1;
    vis[u]=0;
    return ans;
}

int main()
{
    scanf("%d",&n);
    for(int i=1;i