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

1. 문제

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

9466번: 텀 프로젝트

 

2. 알고리즘 분류

• 그래프 이론
• 그래프 탐색
• 깊이 우선 탐색

 

3. 소스 코드

#include <iostream>
#include <cstring>

using namespace std;

int ans;
int choice[100001];
bool visited[100001];
bool done[100001];

void dfs(int cur)
{
	visited[cur] = true;

	int next = choice[cur];

	if (!visited[next]) // 선택한 학생 계속 탐색
		dfs(next);
	else if (!done[next]) // 이미 카운팅된 학생이 아니고, 이전에 탐색했던 학생일 때
	{
		// 다시 탐색하면서 카운팅 시작
		for (int i = next; i != cur; i = choice[i]) {
			ans++;
		}
		ans++;	// 현재 위치 카운팅
	}

	done[cur] = true;	// 중복 카운팅 방지용 Done 플래그
}

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

	int T, n;
	cin >> T;

	// Test Case 반복
	while (T--)
	{
		// 초기화
		memset(visited, false, sizeof(visited));
		memset(done, false, sizeof(done));
		ans = 0;

		// n : 학생의 수 입력
		cin >> n;

		// 선택한 학생 입력
		for (int i = 1; i <= n; i++)
			cin >> choice[i];


		// 모든 학생 탐색
		for (int i = 1; i <= n; i++)
		{
			// 탐색하지 않은 학생만 DFS 탐색
			if (!visited[i])
				dfs(i);
		}

		// 총 학생 수에서 팀을 이룬 학생 뺀 값을 출력
		cout << n - ans << '\n';
	}

	return 0;
}