[BOJ 9466] 텀 프로젝트

출처 : https://www.acmicpc.net/problem/9466

#include <iostream>

#include <algorithm>

#include <memory.h>

using namespace std;

int N, arr[100001], result;

bool check[100001], e[100001];

void dfs(int now)

{

check[now] = true;

if (check[arr[now]])

{

if (!e[arr[now]])

{

for (int i = arr[now]; i != now; i = arr[i]) result++;

result++;

}

}

else dfs(arr[now]);

e[now] = true;

}

int main()

{

int t = 1; int T;

cin >> T;

while (T--)

{

result = 0; memset(arr, 0, sizeof(arr));

memset(check, false, sizeof(check)); memset(e, false, sizeof(e));

cin >> N;

for (int i = 1; i <= N; i++) cin >> arr[i];

for (int i = 1; i <= N; i++)

{

if (!check[i]) dfs(i);

}

cout << N-result << endl;

}

return 0;

}