[C++] 백준 9466번 텀 프로젝트

9466번: 텀 프로젝트

그래프 탐색 문제.

그래프 내의 Cycle의 존재를 찾은 후에 해당 Cycle에서 몇 개의 노드가 존재하는 지 찾아서 해결하면 된다.

 

문제 풀이

나같은 경우에는 다음과 같은 방법으로 해결할 수 있었다.

• 그래프 탐색을 돌면서 각 수가 만나는 마지막 번호를 기록한다.
  • 이 때, 다음 번호가 이미 방문된 번호라면 현재 번호를 Return한다. (해당 번호에서 Cycle이 발생했다는 뜻)
• 그 후 각 수가 만나는 마지막 번호들에 대해 그래프 탐색을 진행해서 노드의 개수를 찾는다.

/*
* 백준 9466번 텀 프로젝트
* https://www.acmicpc.net/problem/9466
* - 그래프 탐색
*/
#include <iostream>
#include <vector>

using namespace std;

int studentChoice[100001];
int studentLast[100001];
bool visit[100001];
bool visitForResult[100001];
int result;

int go(int curNum) {
	int nxtNum = studentChoice[curNum];

	if (visit[curNum]) return curNum;

	visit[curNum] = true;

	if (studentLast[nxtNum] == -1) {
		return studentLast[curNum] = go(nxtNum);
	}
	else {
		return studentLast[curNum] = studentLast[nxtNum];
	}
}

int checkCycleCnt(int curNum, int curCnt) {
	int nxtNum = studentChoice[curNum];

	if (curNum == nxtNum) return 1;

	visitForResult[curNum] = true;

	if (!visitForResult[nxtNum]) {
		return checkCycleCnt(nxtNum, curCnt + 1);
	}
	else {
		return curCnt;
	}
}

int main() {
	int tCnt;
	cin >> tCnt;

	while (tCnt--) {
		int studentCnt;
		cin >> studentCnt;

		result = studentCnt;

		for (int i = 1; i <= studentCnt; i++) {
			cin >> studentChoice[i];
			studentLast[i] = -1;
			visit[i] = false;
			visitForResult[i] = false;
		}

		for (int i = 1; i <= studentCnt; i++) {
			if (studentLast[i] == -1) {
				go(i);
			}
		}

		for (int i = 1; i <= studentCnt; i++) {
			int num = studentLast[i];
			if (!visitForResult[num]) {
				visitForResult[num] = true;
				result -= checkCycleCnt(num, 1);
			}
		}

		cout << result << "\n";
	}
	return 0;

}