https://vjudge.net/problem/CodeForces-1249B2
题目大意：从一列数的第i个数开始，然后移动到第ai个数，这样不断移动下去回到第i个数需要经过多少次。
显然从i->i中的所有数可以组成一个圆环，所有圆环中的元素需要移动的次数是一样的，所以对于每一个没有搜索过的数来说，在搜索过程中出现的数字需要移动的次数是一样的，我们把这些结果记 录下来，避免重复搜索，就可以做到O(n)的复杂度了。
#include<set> #include<map> #include<stack> #include<queue> #include<cmath> #include<cstdio> #include<cctype> #include<string> #include<vector> #include<climits> #include<cstring> #include<cstdlib> #include<iostream> #include<algorithm> #define endl '\n' #define max(a, b) (a > b ? a : b) #define min(a, b) (a < b ? a : b) #define mst(a) memset(a, 0, sizeof(a)) #define IOS ios::sync_with_stdio(false) #define _test printf("~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~\n") using namespace std; typedef long long ll; typedef pair<int, int> P; const double pi = acos(-1.0); const double eps = 1e-7; const ll MOD = 1e9+7; const int INF = 0x3f3f3f3f; const int _NAN = -0x3f3f3f3f; const int NIL = -1; const int maxn = 2e5+10; int arr[maxn], ans[maxn], cnt; void solve(int x, int pos) { if (x != arr[pos]) { ++cnt; solve(x, arr[pos]); } ans[pos] = cnt; } int main(void) { int t; scanf("%d", &t); while(t--) { int n; scanf("%d", &n); for (int i = 1; i<=n; ++i) scanf("%d", &arr[i]); for (int i = 1; i<=n; ++i) if (!ans[i]) { cnt = 1; solve(i, i); } for (int i = 1; i<=n; ++i) printf(i == n ? "%d\n" : "%d ", ans[i]); mst(ans); } return 0; }