1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
| #include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 200010;
int T, n;
int p[N], s[N];
int find(int x) {
if (p[x] != x) p[x] = find(p[x]);
return p[x];
}
int main() {
scanf("%d", &T);
while (T--) {
scanf("%d", &n);
for (int i = 1; i <= n; ++i) p[i] = i, s[i] = 1;
for (int i = 1; i <= n; ++i) {
int j;
scanf("%d", &j);
if (find(i) != find(j)) {
s[find(j)] += s[find(i)];
p[find(i)] = find(j);
}
}
for (int i = 1; i <= n; ++i)
printf("%d ", s[find(i)]);
puts("");
}
return 0;
}
|