[10451] 순열 사이클

https://www.acmicpc.net/problem/10451

10451번: 순열 사이클

입력은 방향그래프가 들어온다. 아래와 같이 들어오면 3을 출력하면 된다.

 

 

 

 

예제의 두번째 그래프는 아래와 같다.

자기 자신을 가리키는 노드는 그림에는 없지만, 5개로 그림의 2개와 더해 7이 정답이다.

 

<소스코드>

#include<stdio.h>
#include<string.h>
int n, a[1001];
bool visit[1001];
void f(int cur) {
    visit[cur] = true;
    int i;
    int next = a[cur];
    if (visit[next] == false) {
        f(next);
    }
    return;
}
int main(void) {
    int i,t;
    scanf("%d", &t);
    while (t--) {
        scanf("%d", &n);
        memset(visit, false, sizeof(visit));
        for (i = 1; i <= n; i++)
            scanf("%d", &a[i]);
        int cnt = 0;
        for (i = 1; i <= n; i++) {
            if (visit[i] == false) {
                f(i);
                cnt++;
            }
        }
        printf("%d\n", cnt);
    }
    return 0;
}

재귀함수를 이용해 구현하였다.