백준 9466: 텀 프로젝트

문제 요약

학생들이(s1, s2, ..., sr)이라 할 때, r=1이고 s1이 s1을 선택하는 경우나, s1이 s2를 선택하고, s2가 s3를 선택하고,..., sr-1이 sr을 선택하고, sr이 s1을 선택하는 경우에만 한 팀이 될 수 있다.

주어진 선택의 결과를 보고 어느 프로젝트 팀에도 속하지 않는 학생들의 수를 계산하는 프로그램을 작성하라.

문제 분류

• 그래프 이론
• 그래프 탐색
• DFS

문제 풀이

DFS하면서 사이클을 찾아내는 문제이다. 일반적인 DFS에서 k번째 원소를 방문하였는지 여부의 visited[]를 선언하는 것과 더하여 k번째에서 DFS를 완료하였는지의 여부를 가려내는 finished[]를 선언하여 사이클을 판단한다.

즉, visited[k]가 true이면서, finished[k]가 false이면 방문한 적이 있으면서 아직 DFS탐색이 끝나지 않은, 사이클을 발견하게 되는 것이다.

해당 사이클을 형성하는 원소의 개수를 세고, 전체 개수 n에서 빼주면 된다.

풀이 코드

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

using namespace std;

bool visited[100001], finished[100001];
int map[100001];
int cnt, n;

void dfs(int k) {
	if (k == map[k]) {
		if (!visited[k]) {
			visited[k] = true;
			finished[k] = true;
			cnt++;
		}
		return;
	}
	visited[k] = true;
	if (!visited[map[k]])
		dfs(map[k]);
	else {
		if (!finished[map[k]]) {
			for (int it = map[k]; it != k; it = map[it]) cnt++;
			cnt++;
		}
	}
	finished[k] = true;
}

int main()
{
	int t, n;
	cin >> t;

	while (t--) {
		scanf("%d", &n);
		cnt = 0;
		fill_n(visited, n + 1, 0);
		fill_n(finished, n + 1, 0);
		for (int i = 1; i <= n; i++) {
			scanf("%d", map + i);
		}
		for (int i = 1; i <= n; i++) {
			if (!visited[i])
				dfs(i);
		}
		printf("%d\n", n - cnt);
	}

	return 0;
}