(c++) 백준 9466번: 텀 프로젝트

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

9466번: 텀 프로젝트

[풀이]

dfs를 이용하여 풀었다.

다음 학생이 처음 방문하는 학생이면 check[학생번호]를 true로 바꾸어주고,

이미 한 번 방문했던 학생을 다시 방문하게 된다면 Recheck[학생번호]가 false일 경우 거쳐왔던 학생만큼 cnt에 저장한다.

(cnt는 프로젝트 팀에 속한 학생들의 수이다)

※dfs마지막에 Recheck[현재 학생번호]를 true로 바꿔줘야 같은 싸이클을 그 싸이클에 속하는 원소가 나올때마다 더하는 걸 막을 수 있다.

 

include <iostream>
#include <cstring>//memset
using namespace std;
#define Max 100001

int T, n;
int Student[Max];//어떤 학생이 어떤 학생을 선택했는지 저장
bool check[Max], Recheck[Max];
int cnt;//프로젝트 팀에 속하는 학생 수

void dfs(int sNum) {
	int next = Student[sNum];
	check[sNum] = true;

	if (check[next] == false) {
		dfs(next);
	}
	//이미 한 번 체크한 학생이면
	else {
		//이미 재방문했던 학생이 아니라면
		if (!Recheck[next]) {
			for (int i = next; i != sNum; i = Student[i])cnt++;
			cnt++;
		}
	}
	Recheck[sNum] = true;//다시 이 수가 나와도 cnt못 세도록
}

void solution() {
	cin >> T;
	while (T--) {
		memset(check, false, sizeof(check));
		memset(Recheck, false, sizeof(Recheck));
		cin >> n;
		for (int i = 1; i <= n; i++) {
			cin >> Student[i];
		}
		cnt = 0;
		for (int i = 1; i <= n; i++) {
			if (!check[i])
				dfs(i);
		}
		cout << n - cnt << endl;
	}
}

int main() {
	solution();
	return 0;
}