[ BOJ ][JAVA][10451] 순열 사이클

www.acmicpc.net/problem/10451

10451번: 순열 사이클

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
1 초	256 MB	12397	7836	5614	63.029%

문제

1부터 N까지 정수 N개로 이루어진 순열을 나타내는 방법은 여러 가지가 있다. 예를 들어, 8개의 수로 이루어진 순열 (3, 2, 7, 8, 1, 4, 5, 6)을 배열을 이용해 표현하면 (1234567832781456) 와 같다. 또는, Figure 1과 같이 방향 그래프로 나타낼 수도 있다.

순열을 배열을 이용해 (1…i…nπ1…πi…πn) 로 나타냈다면, i에서 πi로 간선을 이어 그래프로 만들 수 있다.

Figure 1에 나와있는 것 처럼, 순열 그래프 (3, 2, 7, 8, 1, 4, 5, 6) 에는 총 3개의 사이클이 있다. 이러한 사이클을 "순열 사이클" 이라고 한다.

N개의 정수로 이루어진 순열이 주어졌을 때, 순열 사이클의 개수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 순열의 크기 N (2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄에는 순열이 주어지며, 각 정수는 공백으로 구분되어 있다.

출력

각 테스트 케이스마다, 입력으로 주어진 순열에 존재하는 순열 사이클의 개수를 출력한다.

예제 입력 1

2
8
3 2 7 8 1 4 5 6
10
2 1 3 4 5 6 7 9 10 8

예제 출력 1

3
7

코드

import java.io.*;
import java.util.*;

public class p10451 {
    static BufferedReader br;
    static StringTokenizer st;
    static int T, N;
    static List<Integer>[] list;
    static boolean[] visit;
    public static void main(String[] args) throws IOException {
        br = new BufferedReader(new InputStreamReader(System.in));
        T = Integer.parseInt(br.readLine());
        for (int tc = 0; tc < T; tc++) {
            N = Integer.parseInt(br.readLine());
            list = new ArrayList[N + 1];

            for (int i = 1; i <= N; i++) {
                list[i] = new ArrayList<>();
            }

            st = new StringTokenizer(br.readLine());
            for (int i = 1; i <= N; i++) {
                int v = Integer.parseInt(st.nextToken());

                list[i].add(v);
                list[v].add(i);
            }

            visit = new boolean[N + 1];

            int cnt = 0;
            for (int i = 1; i <= N; i++) {
                if (!visit[i]) {
                    dfs(i);
                    cnt++;
                }
            }
            System.out.println(cnt);
        }
    }

    static void dfs(int num) {
        if (visit[num]) {
            return;
        }
        visit[num] = true;
        for (int x : list[num]) {
            if (!visit[x]) {
                dfs(x);
            }
        }
    }
}