F. Permutation Cycles

1 부터 $N$ 까지의 수 $N$개가 포함된 순열이 주어졌을 때 문제에서 정의한 그래프를 그릴 수 있다. 그 그래프에서 포함된 회로(cycle)의 개수를 세는 문제다.

순열로 표현한 그래프의 특징상 회로의 개수는 곧 연결 요소의 개수가 된다. 따라서 DFS, BFS 등 여러 가지 방법으로 Flood-Fill 을 하여 연결 요소의 개수를 구하면 된다.

#include <stdio.h> int T, N; int A[1001]; bool V[1001]; void dfs(int n) { if (V[n]) return; V[n] = 1; dfs(A[n]); } int main() { int i; for (scanf("%d", &T);T--;){ scanf("%d", &N); for (i=1;i<=N;i++) scanf("%d", A+i), V[i] = 0; int ans = 0; for (i=1;i<=N;i++) if (!V[i]) ans++, dfs(i); printf("%d\n", ans); } }

저작자표시

'ICPC > 2014 대전' 카테고리의 다른 글

H. String Transformation  (0)	2014.11.10
G. Road Repair  (0)	2014.11.10
F. Permutation Cycles  (0)	2014.11.09
E. Marbles  (0)	2014.11.09
D. Exploration  (2)	2014.11.09
C. Eureka Theorem  (0)	2014.11.09