[백준/BOJ] 백준 9466번 : 텀 프로젝트

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

9466번: 텀 프로젝트

전체 학생수에서 팀이 만들어지는 학생수를 뺀다

 

코드

#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;

int n;
int adj[100001];
int visited[100001];
int team_check[100001]; //팀이 있는지 없는지 여부가 확인되었는지 체크
int visited_num;

int Solve(int here)
{
	int can_team= 0;

	visited[here] = visited_num; //몇번째로 방문했는지 저장
	visited_num++;

	int there = adj[here];

	if (visited[there] == 0)
		can_team = Solve(there);

	else //방문한적 있는곳으로 왔을때
	{
		//there가 팀이 있는지 없는지 여부가 정해지지 않았을때
		//즉, 지금 순환에서 다시 방문한적 있는곳으로 온것일때
		if (team_check[there] == 0)
		{
			//팀원들의 수를 저장
			can_team = visited[here] - visited[there] + 1;
		}
	}

	//here는 팀이 있는지 없는지 여부가 결정 되었다
	team_check[here] = 1;

	return can_team;
}

void Pre()
{
	memset(visited, 0, sizeof(visited));
	memset(team_check, 0, sizeof(team_check));
	visited_num = 1;
}

int main()
{
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);

	int tc;
	int temp;
	int result;

	cin >> tc;

	for (int t = 0; t < tc; t++)
	{
		Pre();

		cin >> n;
		result = n; //전체 학생들에서 팀이 만들어지는 학생수를 뺼것이므로 일단 전체 학생수를 저장

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

		for (int i = 1; i <= n; i++)
		{
			if (visited[i] != 0)
				continue;

			//팀이 만들어지는 학생수를 뺸다
			result -= Solve(i);
		}

		cout << result << "\n";
	}

	return 0;
}