codeforces 595 B2 Books Exchange (hard version)

这道题的意思就是有n本书，每本书都有自己的编号，每次可以移动一本书，把这个本书移动到当前编号对应的位置，求移动几次可以使得编号和位置对应起来。

比如样例

3

2 3 1

2第一次跑到第二个位置对应值为3，然后再跑到3的位置，对应值为1,1就跑到1.所以移动三次。

这样就是找环，然后输出环的大小，我开始t了一次，因为hard版数据大，暴力跑是会超时的。

通过递归找环，在找的时候就记录路径，然后再找的时候就把每个位置的给记录下下，然后赋值就行。

AC代码：

#include<cstdio>
#include<cstring>
#include<iostream>
#include<math.h>
using namespace std;
typedef long long ll;
typedef double ld;
int n,m;
int i,j,k;
int a[200010];
int ans[200010];
int cnt,res;
int t;
int slove(int stdd, int nowid, int toid, int step)
{
    if(stdd==toid)
        return ans[nowid]=step;
    return ans[nowid]=slove(stdd, toid, a[toid], step+1);
}
 
 
int main()
{
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d",&n);
        memset(ans,0,sizeof ans );
        for(i=1; i<=n; i++)
            scanf("%d",&a[i]);
        for(i=1; i<=n; i++)
        {
            if(ans[i]==0)
            {
                slove(i,i,a[i],1);
            }
        }
 
        for(i=1; i<n; i++)
            printf("%d ",ans[i]);
        printf("%d\n",ans[n]);
    }
    return 0;
}