CF1249B2 Books Exchange (hard version) 题解

题目大意

共 $q$ 组询问，对于每一组询问有长度为 $n$ 的序列 $p$，$p_i$ 表示第 $i$ 个人的下一位是 $p_i$。

求每一个点所在环的长度。

关于解法

本题是一道记忆化搜索题（我不会 Tarjan 缩点），从而减少时间复杂度。题目大意请参考 CF1249B1。

我们发现如果暴力搜索的话对于每一个点我们都会一直搜索直到环，而这个算法会让有许多点重复走过多次，是没有意义的，所以我们想到了记忆化搜索。

暴力搜索时间复杂度是 $O(\sum n^2)$，记忆化搜索的时间复杂度是 $O(\sum 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;
}