[BOJ/C++] 9466 텀 프로젝트 : DFS

문제

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

풀이

학생이 한 명만 선택하므로 인접리스트 만들 필요없이 그냥 배열에 저장하면 됨

🌟done 배열 : 더 이상 방문하지 않을 것을 확신하는 경우에 true => 팀 매칭이 완료된 경우

방문은 했지만, 팀 매칭이 완료되지 않은 경우에 사이클에 포함된 노드 수 셈

🥝처음 보는 조건을 가진 for문!

for (int i = next; i != node; i = arr[i]) { //사이클에 속한 인원 확인
	cnt++;
}

1	2	3	4	5	6	7
3	1	3	7	3	4	6

dfs(4)->dfs(7)->dfs(6)
node=6, next=4

i = next = 4
i = arr[4] = 7
i = arr[7] = 6 //반복문 탈출

코드

#include <iostream>
#include <vector>
#include <string.h>
#include <algorithm>

using namespace std;

int arr[100001];
bool check[100001];
bool done[100001];
int cnt;

void dfs(int node) {
	check[node] = true;

	int next = arr[node];

	if (!check[next]) {
		dfs(next);
	}
	else if (!done[next]) { //방문은 했지만, 팀 매칭이 완료되지 않은 경우
		for (int i = next; i != node; i = arr[i]) { //사이클에 속한 인원 확인
			cnt++;
		}
		cnt++; //사이클 시작 학생 추가
	}

	done[node] = true; //팀 매칭 완료
}

int main() {
	int T;

	cin >> T;
	while (T--) {
		int n;

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

		for (int i = 1; i <= n; i++) {
			if (!check[i]) {
				dfs(i);
			}
		}

		cout << n - cnt << '\n';

		//초기화
		cnt = 0;
		memset(arr, 0, sizeof(arr));
		memset(check, false, sizeof(check));
		memset(done, false, sizeof(done));
		
	}

	return 0;
}