[백준] 9466번 텀 프로젝트 C++ 문제풀이

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

9466번: 텀 프로젝트

문제 풀이

DFS를 이용했는데, 이 문제의 핵심은 마지막 순서의 노드는 무조건 순환을 이룬다는 것이다.

Visited 배열을 이용해 방문 여부를 확인하고 재귀문 안에서 방문을 했었는데 순환 그래프를 아직 확인하지 않았다면 done 배열을 이용해 순환그래프를 이루는 노드들을 count 해주었다. 마지막으로는 조건문 밖에 done[x] = true를 통해 순환 여부를 확인했음을 코드로 작성했다 

소스 코드

#include <iostream>
#include <vector>
using namespace std;

int cnt = 1;
int n;
vector<int> student[100001];
bool visited[100001] = { false }; //방문 여부를 확인
bool done[100001] = { false }; //순환 여부를 확인했다는 것을 확인!

void init() {
	for (int i = 1; i <= n; i++) {
		visited[i] = false;
		done[i] = false;
		student[i].clear();
	}
}

void dfs(int x) {
	visited[x] = true;
	int next_num = student[x][0];
	if (visited[next_num] == false)
		dfs(next_num);
	else {
		if (done[next_num] == false) {
			while (next_num != x) {
				next_num = student[next_num][0];
				cnt += 1;
			}
			cnt++;
		}
	}
	done[x] = true;
}

int main() {
	ios::sync_with_stdio(false); 
	cin.tie(NULL); 
	cout.tie(NULL);
	
	int T;
	cin >> T;
	for (int i = 0; i < T; i++) {
		cin >> n;
		for (int j = 1; j <= n; j++) {
			int a;
			cin >> a;
			student[j].push_back(a);
		}
		cnt = 0;
		for (int j = 1; j <= n; j++)
			if (!visited[j])
				dfs(j);

		cout << n - cnt << endl;

		init();
	}
}