출처 BOJ

텀 프로젝트

문제

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

학생들이($s_{1}, ..., s_{r}$)이라 할 때, r=1이고 $s_{1}$이 $s_{1}$을 선택하는 경우나, $s_{1}$이 $s_{2}$를 선택하고, $s_{2}$가 $s_{3}$를 선택하고,…, $s_{r-1}$이 $s_{r}$을 선택하고, $s_{r}$이 $s_{1}$을 선택하는 경우에만 한 팀이 될 수 있다.

예를 들어, 한 반에 7명의 학생이 있다고 하자. 학생들을 1번부터 7번으로 표현할 때, 선택의 결과는 다음과 같다.

위의 결과를 통해 (3)과 (4, 7, 6)이 팀을 이룰 수 있다. 1, 2, 5는 어느 팀에도 속하지 않는다.

주어진 선택의 결과를 보고 어느 프로젝트 팀에도 속하지 않는 학생들의 수를 계산하는 프로그램을 작성하라.

입력

첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫 줄에는 학생의 수가 정수 n (2 ≤ n ≤ 100,000)으로 주어진다. 각 테스트 케이스의 둘째 줄에는 선택된 학생들의 번호가 주어진다. (모든 학생들은 1부터 n까지 번호가 부여된다.)

출력

각 테스트 케이스마다 한 줄에 출력하고, 각 줄에는 프로젝트 팀에 속하지 못한 학생들의 수를 나타내면 된다.

예제

범위체크

연산 없음

풀이

cycle에 속한 경우 → 팀 가능
cycle에 안 속한 경우 → 팀 불가능

각 노드를 지나가는데 걸린 횟수를 cnt배열에 저장

• 각 노드의 state를 3가지로 나타낼 수 있음.
  • 탐색 안한 경우 : 0
    cnt값 증가, 시작이랑 같은 지 확인(같으면 값리턴, 아니면 재귀)
  • 탐색 중인 경우 : 1
    다시 지나갈 경우, 지금cnt - 이전cnt(사이클을 구성하는 노드 개수)
  • 탐색 끝난 경우 : -1
    탐색한 노드들은 -1로 표시해서 다시 돌지 않게 만듦

코드

code

#include<cstdio>
#define BOUND 100001

using namespace std;

int N,Cnt;
int G[BOUND],cnt[BOUND],check[BOUND];

void dfs(int now, int start, int num){
	num++;
	if(check[now] == 1)
		Cnt += (num - cnt[now]);
	else if(check[now] == -1)
		Cnt += 0;
	else{
		check[now] = 1;
		cnt[now] = num;

		if(start == now)
			Cnt += cnt[now];
		else
			dfs(G[now],start,num);
	}
	check[now] = -1;
}

int main(){
	int testcase;
	scanf("%d",&testcase);
	while(testcase--){
		scanf("%d",&N);
		Cnt = 0;
		for(int i=0; i<N; i++){
			scanf("%d",&G[i]);
			G[i] = G[i] -1;
			check[i] = 0;
			cnt[i] = 0;
		}
		
		for(int i=0; i<N; i++){
			if(check[i] == 0)
				dfs(G[i],i,0);
			check[i] = -1;
		}

		printf("%d\n",N-Cnt);	
	}
}

복잡도

$O(N)$
모든 노드 1번씩만 지나가면서 값을 구하기 때문에