[BOJ] 9466 - 텀 프로젝트

1. 문제 해석

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

9466번: 텀 프로젝트

• 1~n번까지 학생이 있다. 각자 원하는 팀원의 번호를 선택해야 한다.
• 각 팀원들의 선택이 사이클을 형성하면 팀이 결성된다.(자신을 선택해도 사이클이 형성됨)
• 팀을 결성하지 못한 학생의 수를 구하는 문제이다.

2. 접근방법

• 1번부터 n번까지 각 학생을 시작으로 한 DFS 탐색을 통하여 사이클이 존재하는지 확인하다. 
• 사이클이 확인되면 사이클의 시작이 되는 학생의 번호를 저장하여 팀원 구성이 완료된 학생 수를 저장해둔다.
• 방문 표시를 통해서 이미 확인이 완료된 학생은 탐색하지 않는다.

 

3. 주의할 점

• n <= 100,000이고, 여러 개의 테스트 케이스를 수행해야 하기 때문에 이미 팀원 구성을 확인한 학생까지 탐색하면 시간 초과가 발생할 수 있다.

 

4. 소스코드

#include <iostream>
#include <vector>

using namespace std;

int N;
int a[100001];
bool vis[100001];
bool chk[100001];
bool isOk;
int cycleStartNum;
int cycleCnt;

void init() {
	cycleCnt = 0;
	for (int i = 0; i < 100001; i++) chk[i] = vis[i] = false;
}

void dfs(int i) {
	if (chk[i]) return;
	if (vis[i]) {
		isOk = true;
		cycleStartNum = i;
		return;
	}

	vis[i] = true;
	dfs(a[i]);
	chk[i] = true;
	if (isOk) {
		cycleCnt++;
		if (i == cycleStartNum) isOk = false;
	}
}

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

	int T;
	cin >> T;
	while (T--) {
		init();
		cin >> N;
		for (int i = 1; i <= N; i++) cin >> a[i];
		for (int i = 1; i <= N; i++) {
			if (!vis[i]) {
				isOk = false;
				cycleStartNum = 0;
				dfs(i);
			}
		}
		cout << N - cycleCnt << '\n';
	}

	return 0;
}