@[six_小6猪](/user/191993) 其实我觉得可以先循环找环，把环上的ans先计算掉再去处理剩余的
by bamboo1030 @ 2022-08-23 09:23:35
@[bamboo123](/user/369181)
```cpp
#include<iostream>
#include<cstdio>
#include<stack>
using namespace std;
stack <int > k;
bool d[1000005];
int f[1000005];
int ans[1000005];
int s[1000005];
int z;
int mem(int n)
{
for(int i=1;i<=n;i++)
d[i]=0;
}
int tot=0;
void dfs(int x)
{
d[x]=1;
k.push(x);
while(1)
{
int y=f[x];
if(ans[y]>0)
{
ans[x]=ans[y]+1;
return;
}
if(d[y]==1)
{
while(1)
{
s[++z]=k.top();
if(s[z]==y)
{
for(int i=1;i<=z;i++)
ans[s[i]]=z;
return;
}
k.pop();
}
return ;
}
k.push(y);
d[y]=1;
x=y;
}
}
void dfss(int x)
{
ans[x]++;
int y=f[x];
if(ans[y]>0)
{
ans[x]+=ans[y];
return ;
}
dfss(y);
ans[x]+=ans[y];
}
void nen()
{
for(int i=0;i<=z+1;i++)
s[i]=0;
z=0;
while(!k.empty())
k.pop();
}
int main()
{
int n;
cin>>n;
for(int i=1;i<=n;i++)
{
int a;
cin>>a;
f[i]=a;
}
for(int i=1;i<=n;i++)
{
if(ans[i]==0)
{
mem(n);
nen();
dfs(i);
}
}
for(int i=1;i<=n;i++)
{
if(ans[i]>0)
cout<<ans[i]<<endl;
else
{
mem(n);
dfss(i);
cout<<ans[i]<<endl;
}
}
}
```
这是我之前的一个代码大概也是先找环，但这个只有40
by six_小6猪 @ 2022-08-23 09:42:34
@[six_小6猪](/user/191993)
对于 TLE 的测试点，您的函数：
```
int mem(int n)
{
for(int i=1;i<=n;i++)
d[i]=0;
}
```
一共执行了 `50007` 次，需要提高算法的效率才能通过该测试点。
by metaphysis @ 2022-08-25 20:56:44
而 `dfs` 函数则是整整执行了 `100000` 次。
by metaphysis @ 2022-08-25 20:59:40
@[metaphysis](/user/333388) 谢谢。您的意思也就是时间复杂度不对，要换更好的算法，我还以为在哪写挂了。
by six_小6猪 @ 2022-08-26 06:51:53