C++ 洛谷 P2921 [USACO08DEC]在农场万圣节Trick or Treat on the Farm 题解

P2921 [USACO08DEC]在农场万圣节Trick or Treat on the Farm

分析：

这棵树上有且仅有一个环

两种情况：

1.讨论一个点在环上,如果在则答案与它指向点相同,

2.不在就等于它指向点答案+1,具体就直接大力dfs,

如何求环长度：

终点深度-起点深度=终点起点距离

#include<cstdio>
#include<string>
#include<cstring>
using namespace std;
const int maxn=100005;
int n;
int cnt=1;
int a[maxn];
int h[maxn];
int ans[maxn];
int read() //快读 
{
    int x=0,f=1;char c=getchar();
    while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
    while(isdigit(c)){x=x*10+c-'0';c=getchar();}
    return x*f;
}
void dfs(int i,int deep)
{
    h[i]=deep;   //该点深度 
    if(ans[a[i]]) ans[i]=ans[a[i]]+1;   //若指向点有答案，而自己无答案，则自己不再环上。要+1 
    else if(h[a[i]])       //若形成环 
    {
        ans[i]=(h[i]-h[a[i]]+1);  //刷新该点答案 
        int k=a[i];
        while(i!=k)   //刷新环内所有答案 ，直到回到原点 
        {
            ans[k]=ans[i];
            k=a[k];
        }
    }
    else
    {
        dfs(a[i],deep+1);
        if(!ans[i]) ans[i]=ans[a[i]]+1; //自身肯定不再环上，所以+1 
    }
}
void solve()
{
    for (int i=1;i<=n;i++)
    {
        if(!ans[i]) dfs(i,0);  //若此点未有涉及（无答案），就dfs 
    }
    for (int i=1;i<=n;i++)
    printf("%d\n",ans[i]);
}
void work()
{
    n=read();
    for(int i=1;i<=n;i++)
    {
     a[i]=read();
    }
    solve();
}
int main()
{
    work();
    return 0;
}