백준 No.9466 [텀 프로젝트]

Baekjoon Online Judge No.9466 [텀 프로젝트]

---

 문제 

9466번: 텀 프로젝트 (acmicpc.net)

9466번: 텀 프로젝트

---

 설명 

 

  학생들을 노드라고 하고, 학생들이 각각 본인이 팀을 하고 싶은 상대를 간선으로 표현하였다. 결국, 한 팀이 이루어지기 위해선 아래와 같이 싸이클이 이루어져야 한다.

 

  빨간 간선들이 팀을 의미한다. {1, 2, 4} 세 명 이서 한 팀을, {3} 혼자서 한 팀을 이렇게 총 두 팀을 이루었고, {5, 6, 7}은 모두 팀을 이루지 못 했다. 처음에 정답을 우선 n (학생의 수) 로 초기화를 해 둔 후 사이클(팀) 에 있는 학생들의 수를 빼줌으로써 정답을 구했다.

 

  풀이정리

1. 첫 번째 학생부터 마지막 학생까지 개개인이 팀을 함께 하고싶은 학생을 student[k]에 저장을 하였다.
2.  for 문을 통해 첫 번째 학생부터 마지막 학생까지 DFS 를 통해 사이클을 이루는지 검사를 하였다.
3. 사이클을 이룬다면 DFS 를 통해 계속 탐색을 해 나가다가, 탐색 과정에 있었던 노드와 만나는 순간이 생길 것 이다.
     3-1. 탐색을 시작한 노드와 만나지 않을수도 있다. 이 경우엔 만난 노드보다 이전에 탐색된 노드들은 모두 결국 팀을 구성할 수 없게 된다.
     3-2. 탐색을 시작한 노드와 만난다면 현재 탐색과정에 있던 노드들은 모두 한 팀이다.
     3-3. 탐색되는 노드들을 순서대로 번호를 부여한 후, 이후 탐색했던 노드와 만나면, 두 노드의 순서를 비교하여 이루어진 사이클에 해당되는 총 노드들의 개수를 파악한다.
4. 이러한 방식으로 총 팀에 속해있는 노드들의 개수를 구한 후, 이를 n 값에서 뺀다.

---

 Code 

#include <iostream>
#include <cstring>
#define MAX 100001

using namespace std;

int student[MAX], curList[MAX];
bool visit[MAX];

int dfs(const int s, int cur, int cnt) {
	if (visit[cur]) { // 이미 방문한 학생이라면
		if (curList[cur]) return cnt - curList[cur]; // 지금 팀 짜면서 방문된 학생이라면
		else return 0; // 이전에 이미 방문했던 학생이라면
	}
	else { // 아직 방문하지 않은 학생이라면
		visit[cur] = true;
		curList[cur] = cnt;
		int temp = dfs(s, student[cur], cnt + 1);
		curList[cur] = 0;
		return temp;
	}
}

int solve(const int& n) {
	int ret = n;

	for (int i = 1; i <= n; i++) {
		if (visit[i]) continue;
		ret -= dfs(i, i, 1);
	}

	return ret;
}

void Memset_function() {
	memset(student, 0, sizeof(student));
	memset(visit, false, sizeof(visit));
}

int main() {
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

	int tc, n;

	cin >> tc;

	while (tc--) {
		cin >> n;

		Memset_function();

		for (int i = 1; i <= n; i++) {
			cin >> student[i];
		}

		cout << solve(n) << '\n';
	}
}