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

#include <iostream>
#include <string.h>
 
int t = 0;
int n = 0;
int graph[100001] = {};
bool visited[100001] = {};
bool clear[100001] = {};
int count = 0;
 
void DFS(int node) 
{
	visited[node] = true;
	int next = graph[node];
 
	if (!visited[next])
	{
		DFS(next);
	}
 
	else if (!clear[next]) 
	{
		for (int i = next; i != node; i = graph[i]) 
		{
			++count;
		}
 
		++count;
	}
 
	clear[node] = true;
}
 
 
int main() 
{
	std::ios::sync_with_stdio(false);
	std::cin.tie(NULL);
	std::cin >> t;
 
	while (t--) 
	{
		std::cin >> n;
 
		for (int i = 1; i <= n; ++i) 
		{
			std::cin >> graph[i];
		}
 
		for (int i = 1; i <= n; ++i) 
		{
			if (!visited[i]) 
			{
				DFS(i);
			}
		}
 
		std::cout << n - count << '\n';
 
		count = 0;
 
		memset(visited, false, sizeof(visited));
		memset(clear, false, sizeof(clear));
	}
 
	return 0;
}

 

DFS로 돌아서 한번만 돌립니다.

visit을 두 가지로 만들어서 처음 회전 때 visited를 true로 하고 두 분째 회전 때 clear를 true합니다.

이후 clear가 확인된다면 DFS 회전하면서 나온 수를 count로 계산하고 빠져 나옵니다.