백준 - 10451번 - 순열 사이클

10451번

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

public class Main {
	static StringBuilder sb = new StringBuilder();
	static boolean[][] graph;
	static boolean[] check;
	static int a, M;

	public static void main(String[] args) throws IOException {
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(bf.readLine());

		for (int i = 0; i<N; i++) {
			M = Integer.parseInt(bf.readLine());
			graph = new boolean[M+1][M+1];
			check = new boolean[M+1];
			StringTokenizer st = new StringTokenizer(bf.readLine());
			for (int j = 1; j<M+1; j++) {
				a = Integer.parseInt(st.nextToken());
				graph[a][j] = graph[j][a] = true;
			}

			int cnt = 0;
			dfs(1);
			cnt++;
			for (int j = 1; j<check.length; j++) {
				if (!check[j]) {
					dfs(j);
					cnt++;
				}
			}
			sb.append(cnt).append('\n');
		}
		System.out.println(sb);
	}
	static void dfs(int N) {

		check[N] = true;

		for (int i = 0; i<M+1; i++) {
			if (graph[N][i] && !check[i]) {
				dfs(i);
			}
		}
	}
}

풀이

---

순열 사이클이 몇개 있는지 구하는 문제다.

이건 저번에 풀었다. 정점 연결덩어리가 몇개있는지랑 비슷하다. 다른점은 그 연결덩어리가 사이클처럼 참조하는 구조라는것이다.

뭐 그치만 상관없이 dfs로 탐색해서 check 배열에 false가 있으면 dfs한번더 돌리고 cnt를 카운트해주는식으로 수월하게 풀 수 있었다.