코드 복사/붙여넣기 하는 당신이 아름답습니다.

9466 : 텀 프로젝트E

풀이

위상정렬을 하자!

코드

#include <stdio.h>
#include <memory.h>

const int n_ = 100000 + 1;

int ans, a[n_], idg[n_];
bool chk[n_];

void dfs(int n) {
	chk[n] = true;
	++ans, --idg[a[n]];
	if (!chk[a[n]] && !idg[a[n]]) dfs(a[n]);
}

int main() {
	int t, n, i, j;
	scanf("%d", &t);
	for (i = 1; i <= t; ++i) {
		ans = 0;
		scanf("%d", &n);
		memset(chk, 0, sizeof(chk));
		memset(idg, 0, sizeof(idg));
		for (j = 1; j <= n; ++j) {
			scanf("%d", &a[j]);
			++idg[a[j]];
		}
		for (j = 1; j <= n; ++j) if (!chk[j] && !idg[j])
			dfs(j);
		printf("%d\n", ans);
	}

	return 0;
}

아무말

백준, 백준 온라인 저지, BOJ, Baekjoon Online Judge, C, C++, 씨, 씨쁠쁠, JAVA, algorithm, 자바, 알고리즘, 자료구조, 문제, 문제 풀이, 풀이

wookje.kwon's profile image

wookje.kwon

2017-04-18 13:56

Read more posts by this author