BOJ 9466_텀 프로젝트

9466번: 텀 프로젝트

이번 가을학기에 '문제 해결' 강의를 신청한 학생들은 텀 프로젝트를 수행해야 한다. 프로젝트 팀원 수에는 제한이 없다. 심지어 모든 학생들이 동일한 팀의 팀원인 경우와 같이 한 팀만 있을 수도 있다. 프로젝트 팀을 구성하기 위해, 모든 학생들은 프로젝트를 함께하고 싶은 학생을 선택해야 한다. (단, 단 한 명만 선택할 수 있다.)

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

Description

• 싸이클을 이루는 그룹은 제외하고, 이루지 못하는 학생들의 수를 얻어야 함.

• 시간이 무려 3초지만 O(N)으로 해결해야 함.

• 따라서 한 번 스캔하면서 싸이클을 이루지 못하는 학생들을 체크하고, 싸이클을 따라가다 해당 학생을 만나면 탐색을 중단해야 함.

• vector_name.clear()를 이용해 초기화하는 것이 시간소모 적음.

• 참고자료 LINK

 

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

int T, N;
vector<int> students;

void cal() {
	int answer = 0;
	int group_num = 1;
	vector<bool> visited(N, false);
	vector<int> group(N, 0);
	vector<int> visited_node;	// temporal cycling students

	for (int i = 0; i < N; i++) {

		// if the student already has a group num, skip 
		if (group[i] || visited[i] == true) continue;

		visited_node.clear();
		visited[i] = true;
		visited_node.push_back(i);

		int cur_node = students[i];
		// scan only !visited node && had no group(=0) 
		while (!visited[cur_node] && group[cur_node] == 0) {
			visited[cur_node] = true;
			visited_node.push_back(cur_node);
			cur_node = students[cur_node];
		}

		/*	if origin and destin. same after scan cycle, find where does the cycle starts.
			if it's not the node which starts cycle, put -1 to mark it's not groupable */
		int visited_size = visited_node.size();
		for (int j = 0; j < visited_size; j++) {
			if (visited_node[j] != cur_node) {
				group[visited_node[j]] = -1;
			}
			else {
				for (int k = j; k < visited_size; k++) {
					group[visited_node[j]] = group_num;
				}
				group_num++;
				break;
			}
		}
	}

	for (int i = 0; i < N; i++) {
		if (group[i] < 0) answer++;
	}

	cout << answer << "\n";

	return;
}

int main() {
	ios::sync_with_stdio(false);

	cin >> T;
	for (int i = 0; i < T; i++) {
		cin >> N;
		students = vector<int>(N, 0);

		for (int j = 0; j < N; j++) {
			cin >> students[j];
			students[j] -= 1;
		}
		cal();
	}

	return 0;
}