F. Permutation Cycles

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

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

?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23

#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);     } }