题目大意
共
q
q
q 组询问，对于每一组询问有长度为
n
n
n 的序列
p
p
p，
p
i
p_i
pi 表示第
i
i
i 个人的下一位是
p
i
p_i
pi。
求每一个点所在环的长度。
关于解法
本题是一道记忆化搜索题（我不会 Tarjan 缩点），从而减少时间复杂度。题目大意请参考 CF1249B1。
我们发现如果暴力搜索的话对于每一个点我们都会一直搜索直到环，而这个算法会让有许多点重复走过多次，是没有意义的，所以我们想到了记忆化搜索。
暴力搜索时间复杂度是
O
(
∑
n
2
)
O(\sum n^2)
O(∑n2)，记忆化搜索的时间复杂度是
O
(
∑
n
)
O(\sum n)
O(∑n)。
代码
#include<bits/stdc++.h>
using namespace std;
int e[200010],q,n,cnt,t,f[200010],ans[200010];//记忆化搜索
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;
}
void write(int x)
{
if(x<0) putchar('-'),x=-x;
if(x>9) write(x/10);
putchar(x%10+'0');
return;
}
inline int search(int pos,int t,int cnt)
{
f[pos]=1;
if(t==e[pos]) return ans[pos]=cnt+1;
else return ans[pos]=search(e[pos],t,cnt+1);
}
int main()
{
q=read();
while(q--)
{
n=read();
memset(e,0,sizeof(e)),memset(f,0,sizeof(f));
for(int i=1;i<=n;i++) e[i]=read();
for(int i=1;i<=n;i++) if(!f[i]) search(i,i,0);
for(int i=1;i<=n;i++) write(ans[i]),printf(" ");
printf("\n");
}
return 0;
}
