[BOJ/9466] 텀 프로젝트, c++

 

www.acmicpc.net/problem/9466

9466번: 텀 프로젝트

한줄 후기 : 전에 못 풀던 문제를 다시 풀었는데 맞으면 진짜 기쁘다

 

문제를 잘 읽어보면 결국 한 팀이 된다는건 4->7->6->4 이렇게 한팀 즉, 그래프로 생각했을 때 사이클이 만들어지면 한 팀이 되는 것이다.

그럼 팀에 속하지 못한 학생의 수이니 사이클 탐지를 하며 개수를 세어 전체 수에서 빼주면 답이 된다.

 

//AC
//BOJ 9466 텀 프로젝트
#include <iostream>
#include <vector>
#include <cstring>
using namespace std;
int v[101010];
bool visit[101010];
int pr[101010];
bool cycle[101010];
int cnt = 0;
void dfs(int s){
	visit[s] = true;
	if(!visit[v[s]]){
		pr[s] = v[s];
		dfs(v[s]);
	}
	else if(!cycle[v[s]]){
		for(int i=v[s]; i != s; i = pr[i]){
			cnt++;
		}
		cnt++;
	}
	cycle[s] = true;
}
int main(){
	int T;
	cin >> T;
	while(T--){
		int n;
		cnt = 0;
		scanf("%d", &n);
		for(int i=1; i<=n; i++){
			scanf("%d", &v[i]);			
		}
		for(int i=1; i<=n; i++){
			if(!visit[i]){
				dfs(i);
			}
		}
		printf("%d\n", n-cnt);
		memset(visit, false, sizeof(visit));
		memset(cycle, false, sizeof(cycle));
	}
}

이런게 뿌듯하다니깐요?

 

void dfs(int s){
	visit[s] = true;
	if(!visit[v[s]]){
		pr[s] = v[s];
		dfs(v[s]);
	}
	else if(!cycle[v[s]]){
		for(int i=v[s]; i != s; i = pr[i]){
			cnt++;
		}
		cnt++;
	}
	cycle[s] = true;
}

여기가 사이클 탐지+팀에 속한 사람 수 세는 부분이다.

어차피 한명당 한 사람만 고를 수 있으니 일차원 배열에 그래프를 기록해도 된다.

pr 배열에는 해당 노드가 고른 노드를 넣어주면 된다.

그리고 dfs 가 끝난 노드는 cycle 배열을 true 로 만드는데 만약 이 cycle이 false라면, 즉 내가 고른 노드가 아직 방문하지 않은 노드라면 for문을 돌면서 i = pr[i] 계속 그래프를 타고타고 넘어가다 현재 나와 만날 때 까지 count를 세준다. 

마지막엔 나와 만났으니 나까지 세주면 된다.

결과적으로 n-cnt가 정답이 된다.