3579.数字移动

3579. 数字移动

题目描述：

$ 1 \sim n $ 数组， $ a[i] = i $ ，给出一个位置序列 $ p_1, p_2, \cdots, p_n $ ,重复将 $ a[i] $ 移动到 $ a[p_i] $ 。求出每个数字第一次重新回到位置 $ i $ 的次数。

数据范围：
$ 1\le T \le 1000, 1\le n \le 2 \times 10^5 $

$ \sum n \le 2 \times 10^5 $

题解：

直接对每个位置 dfs 就行，求出每个环的大小，答案就是环的大小。

代码：

using namespace std;
using namespace FAST_IO;
const ll mod = 1e9 + 7;
const int INF = 0x3f3f3f3f;
const ll INF_LL = 0x3f3f3f3f3f3f3f3f;
const double eps = 1e-5;
const int maxn = 2e5 + 10;
const int maxm = 1e5 + 10;
int t, n, m, k;
int a[maxn];
bool vis[maxn];
int ans[maxn];
int cnt;
// 直接dfs搜索，遇到搜过的返回
void dfs(int x)
{
    if (vis[x])
        return;
    vis[x] = 1;
    cnt++;        // 记录环的大小
    dfs(a[x]);    // 下一步
    ans[x] = cnt; // 待递归返回后得到了cnt，记录答案
}
int main()
{
// #define COMP_DATA
#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
#endif
    int tcase;
    read(tcase);
    while (tcase--)
    {
        read(n);
        for (int i = 1; i <= n; i++)
        {
            read(a[i]);
            vis[i] = 0;
        }
        for (int i = 1; i <= n; i++)
        {
            if (!vis[i])
                cnt = 0, dfs(i);
        }
        for (int i = 1; i <= n; i++)
        {
            printf("%d%c", ans[i], " \n"[i == n]);
        }
    }
    return 0;
}