백준 9466 텀 프로젝트 (c++) : 피너클

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

9466번: 텀 프로젝트

까다로운 dfs문제다.

int n, cnt;
bool visited[100001];
bool isCycle[100001];
int arr[100001];

visited는 방문한 학생, isCycle은 학생이 사이클 안에 있는지,

cnt는 사이클안에 있는 학생의 수, n과 arr은 입력받는 값들이다.

int test;
cin >> test;
while (test-- > 0) {
	cin >> n;
	for (int i = 1; i <= n; i++) cin >> arr[i];
	memset(visited, false, sizeof(visited));
	memset(isCycle, false, sizeof(isCycle));
	cnt = 0;

입력을 받고 기본 세팅을 한다.

	for (int i = 1; i <= n; i++) {
			if (!visited[i]) {
				dfs(i);
			}
		}
		cout << n - cnt << '\n';
	}

학생을 하나씩 확인하며 만약 방문하지 않은 학생이라면 dfs를 실행하고

마지막에 전체 학생수(n)에서 사이클 안의 학생수(cnt)를 뺀 수를 출력한다.

void dfs(int now) {
	visited[now] = true;
	if (!visited[arr[now]]) dfs(arr[now]);

dfs다. 현재 학생의 방문을 체크하고 만약 다음 학생을 아직 방문하지 않았다면 다음학생에게 dfs를 실행한다.

	else if(!isCycle[arr[now]]){
		for (int i = arr[now]; i != now; i = arr[i]) {
			cnt++;
			isCycle[i] = true;
		}
		cnt++;
	}
	isCycle[now] = true;

만약 다음 학생이 아직 사이클 안에 있지 않다면

다음 학생을 시작으로 모든 사이클 안의 학생만큼 cnt에 1을 더하고 isCycle에 체크한다.

그리고 현재 학생의 몫도 cnt에 더해준다. (for문에 현재 학생의 경우는 체크되지 않기때문)

마지막으로 현재 학생의 isCycle을 체크해준다. 

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

using namespace std;

int n, cnt;
bool visited[100001];
bool isCycle[100001];
int arr[100001];

void dfs(int now) {
	visited[now] = true;
	if (!visited[arr[now]]) dfs(arr[now]);
	else if(!isCycle[arr[now]]){
		for (int i = arr[now]; i != now; i = arr[i]) {
			cnt++;
			isCycle[i] = true;
		}
		cnt++;
	}
	isCycle[now] = true;
}

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int test;
	cin >> test;
	while (test-- > 0) {
		cin >> n;
		for (int i = 1; i <= n; i++) cin >> arr[i];
		memset(visited, false, sizeof(visited));
		memset(isCycle, false, sizeof(isCycle));
		cnt = 0;
		for (int i = 1; i <= n; i++) {
			if (!visited[i]) {
				dfs(i);
			}
		}
		cout << n - cnt << '\n';
	}
}

전체코드다.