[백준 9466: 텀 프로젝트] - C++

www.acmicpc.net/problem/9466

9466번: 텀 프로젝트

#include<iostream>
using namespace std;

int n = 0;
int cnt = 0;
int arr[100001];
int visited[100001];
int resultArr[100001];

void D(int curNum) {

	visited[curNum] = true;

	int targetNum = arr[curNum]; //현재노드가 가리키고 있는 번호

	if (!visited[targetNum]) //해당 번호를 방문한적 없으면 true
	{
 		D(targetNum);
	}
	else { //이미 방문해서 확인했으면 현재 번호와 연결되어 있는 노드 세기
		if (!resultArr[targetNum])  //이미 노드를 셌다면 패스
		{
			for (int i = targetNum; i != curNum; i = arr[i]) //연결되있는 번호들 확인
			{
				cnt++;//연결된 점들 개수 세기
			}
			cnt++;//자기 자신
		}
	}
	resultArr[curNum] = true;
}
int main()
{
	int total;
	cin >> total;

	for (int index = 0; index < total; index++)
	{
		memset(arr, 0, sizeof(arr));
		memset(visited, 0, sizeof(visited));
		memset(resultArr, 0, sizeof(resultArr));

		cnt = 0;

		cin >> n;
		for (int i = 1; i <= n; i++)
		{
			cin >> arr[i];
		}

		for (int i = 1; i <= n; i++)
		{
			if (visited[i] == false)
			{
				D(i);
			}
		}


		cout << n-cnt << endl;
	}
	return 0;
}