설명
입력
첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 순열의 크기 N (2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄에는 순열이 주어지며, 각 정수는 공백으로 구분되어 있다.
출력
각 테스트 케이스마다, 입력으로 주어진 순열에 존재하는 순열 사이클의 개수를 출력한다.
예시 입력
예시 출력
2
8
3 2 7 8 1 4 5 6
10
2 1 3 4 5 6 7 9 10 8
JavaScript
복사
3
7
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
복사
