[Baekjoon] 10451 순열 사이클

설명

입력

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

출력

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

예시 입력

예시 출력

JavaScript
복사

JavaScript
복사

풀이 과정

간단한 문제입니다.

입력이 주어졌을 때, 각 입력은 순서대로 인덱스와 매핑 됩니다.

해당 인덱스를 하나의 간선이라 생각하고 union-find 알고리즘을 적용하면 쉽게 풀 수 있습니다.

최종 코드

package baekjoon.graph.kruskal;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class _10451 {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine());
        for (int i = 0; i < T; i++) {
            int N = Integer.parseInt(br.readLine());
            int[] parent = new int[N + 1];
            for (int j = 0; j < N + 1; j++) {
	parent[j] = j;
            }
            int cnt = 0;
            StringTokenizer st = new StringTokenizer(br.readLine());
            for (int j = 1; j < N + 1; j++) {
	if (!union(parent, j, Integer.parseInt(st.nextToken()))) {
	    cnt++;
	}
            }
            System.out.println(cnt);
        }
    }

    public static int find(int[] parent, int x) {
        if (parent[x] == x) {
            return x;
        } else {
            return parent[x] = find(parent, parent[x]);
        }
    }

    public static boolean union(int[] parent, int a, int b) {
        int x = find(parent, a);
        int y = find(parent, b);

        if (x != y) {
            if (x > y) {
	parent[y] = x;
            } else {
	parent[x] = y;
            }
            return true;
        }

        return false;
    }

}
JavaScript
복사