68 lines
1.1 KiB
C
68 lines
1.1 KiB
C
#include <stdio.h>
|
|
#include <stdbool.h>
|
|
|
|
int T, N, G;
|
|
int select[100001], result[100001];
|
|
bool visited[100001], done[100001];
|
|
|
|
int solv();
|
|
void dfs(int num);
|
|
|
|
int main() {
|
|
scanf("%d", &T);
|
|
|
|
for(int t=0; t<T; t++) {
|
|
G = 0;
|
|
result[t] = solv();
|
|
}
|
|
|
|
for(int i=0; i<T; i++) printf("%d\n", result[i]);
|
|
|
|
return 0;
|
|
}
|
|
|
|
int solv() {
|
|
scanf("%d", &N);
|
|
|
|
for(int i=1; i<=N; i++) {
|
|
visited[i] = false;
|
|
done[i] = false;
|
|
scanf("%d", &select[i]);
|
|
}
|
|
|
|
for(int n=1; n<=N; n++) {
|
|
if(done[n]) continue;
|
|
dfs(select[n]);
|
|
}
|
|
|
|
return N - G;
|
|
}
|
|
|
|
void dfs(int num) {
|
|
int curr = num;
|
|
|
|
while(true) {
|
|
visited[curr] = true;
|
|
curr = select[curr];
|
|
|
|
if(visited[curr]) {
|
|
if(!done[curr]) {
|
|
int temp = 1;
|
|
int next = select[curr];
|
|
while(next != curr) {
|
|
temp++;
|
|
next = select[next];
|
|
}
|
|
G += temp;
|
|
}
|
|
|
|
break;
|
|
}
|
|
}
|
|
|
|
curr = num;
|
|
while(!done[curr]) {
|
|
done[curr] = true;
|
|
curr = select[curr];
|
|
}
|
|
} |