有 n 人， 每个人都正在读一本独一无二的小h书. 在每一天的结束的时候, 都会进行一次py交易，交易规则为：第 i 的人将给他的书给第 pi 的人 (如果i=pi,那么就是给他自己). 默认pi都是不同的数，是一个1到n的排列. 并且这个p是固定的，不随时间的改变而改变.例如, 如果 n=6 并且 p=[4, 6, 1, 3, 5, 2]，那么第一天结束的时候进行了第一次py交易， 第1个人的书给了第4个人, 第2个人的书给了第6个人，依次类推.。第二天结束的时候，又进行了一次py交易，第1个人的书在第3个人的手里(因为第4个人给了第3个人), 第2个人的书又回到了自己这里（因为第6个人又给了第2个人），依次类推 .
你的任务是确定在第几天后，第i个人的书回到了他自己本身。
例如这个样例: p = [5, 1, 2, 4, 3]. 第一个人的书交易过程如下：
第一天结束的时候第1个人给了第5个人
第二天结束的时候第5个人给了第3个人
第三天结束的时候第3个人给了第2个人
第四天结束的时候第2个人给了第1个人
所以4天后, 第一个人的书回到了他自己本身这里。 第四个人的书1天之后就回到了自己本身（因为当i=4的时候，i=pi）。
你需要回答q个询问
Input
第一行输入一个q（1<=q<=1000），表示q个询问，对于每一个询问：
第一行输入一个n(1<=n<=200000), 表示人的个数
第二行输出n个整数，p1, p2, … , pn.
Output
对于每一个询问，输出n个整数 a1,a2,…,an, ai表示第i个人的书第一次回到了他本身所经历的天数
Example
Input
6 5 1 2 3 4 5 3 2 3 1 6 4 6 2 1 5 3 1 1 4 3 4 1 2 5 5 1 2 4 3
Output
1 1 1 1 1 3 3 3 2 3 3 2 1 3 1 2 2 2 2 4 4 4 1 4
这个如果对于每一个人都进行dfs的话，一定会超时的
所以要进行记忆化搜索
那么如何进行记忆化搜索呢
例如：
5 1 2 4 3
对于一的时候1->5->3->2->1
其实他就构成一个环
对于5的话:5->3->2->1->5
对于这个环上的都是一样的步数
#include<iostream> #include<algorithm> #include<cstring> using namespace std; const int maxn=3e6+100; int a[maxn]; int ans[maxn]; int cnt=0; void dfs(int x,int pos){ if(x!=a[pos]){ cnt++; dfs(x,a[pos]); } ans[pos]=cnt; } int main(){ int t; cin>>t; while(t--){ memset(ans,0,sizeof(ans)); int n; cin>>n; for(int i=1;i<=n;i++){ scanf("%d",&a[i]); } for(int i=1;i<=n;i++){ if(!ans[i]){ cnt=1; dfs(i,i); } } for(int i=1;i<=n;i++){ printf("%d ",ans[i]); } printf(" "); } }