解法
分析一下题目中置换的方式，然后画一下第一个样例的转换路径，会惊奇的发现其实整个图就是数个简单环（不信的可以自己一下题目的样例哦~），那么题目也就可以转换为计算当前节点所处环中的节点数量。
以上内容全部来自与\(yxc\)的视频讲解，我其实在看到题的时候，没啥思路的，但是当听完\(y\)总的讲解之后发现这个思路简直妙到家了，所以记录一样这个题目。
Coding
const int N = 2001000;
int f[N],num[N];
int n;
int find(int x) {
return x == f[x] ? x : f[x] = find(f[x]);
}
int main() {
int t;cin >> t;
while(t--) {
cin >> n;
for(int i = 1;i <= n;++i) f[i] = i,num[i] = 1;
for(int i = 1;i <= n;++i) {
int x = i,y;cin >> y;
x = find(x),y = find(y);
if(x != y) {
num[x] += num[y]; // 这个地方要想清楚怎么加哦~
f[y] = x;
}
}
for(int i = 1;i <= n;++i) {
cout << num[find(i)] << ‘ ‘;
}
cout << endl;
}
return 0;
}