아이디어

(예제 입력 1에 대한 그래프)

• 집합 내의 원소는 순서 상관 없이 모든 원소가 중복되지 않고 포함되어야 하므로 항상 집합 크기와 같은 길이의 사이클이 생긴다.
• 재귀적으로 표를 참조하며 경로를 이으면 위와 같이 규칙을 볼 수 있다.
  • 참조를 타고 자기 자신으로 돌아올 수 있으면 해당 경로는 집합이 된다.
  • 참조를 타고 자기 자신으로 돌아오지 못하고 끊기거나, 무한 루프에 빠지면 해당 경로는 집합에 포함되지 않는다.
• 이러한 조건을 만족하는 시작점들은 모두 집합에 포함된다. 그러므로 그러한 시작점의 개수를 세고, 시작점 번호를 출력하면 된다.

코드

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

public class Main {
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
	static BufferedReader rd = new BufferedReader(new InputStreamReader(System.in));
	static StringBuilder sb = new StringBuilder();

	static int N, s, ans;
	static int[] table;
	static boolean[] visited;
	
	public static void main(String[] args) throws Exception {
		N = Integer.parseInt(rd.readLine());
		
		table = new int[N+1];
		for (int i=1; i<=N; i++) {
			table[i] = Integer.parseInt(rd.readLine());
		}
		visited = new boolean[N+1];
		
		for (int i=1; i<=N; i++) {
			Arrays.fill(visited, false);
			s = i;
			if (dfs(table[i])) {
				ans++;
				sb.append(i).append('\n');
			}
		}
		
		System.out.println(ans);
		System.out.println(sb);
	}
	
	static boolean dfs(int n) {
		if (n == s) return true;
		if (visited[n]) return false;
		visited[n] = true;
		return dfs(table[n]);
	}
}

메모리 및 시간

• 메모리: 14148 KB
• 시간: 120 ms

리뷰

• 위 그림과 같은 아이디어를 발견할 수 있어서 운 좋게 풀은 것 같다.
  • 엄밀하게 증명해보라고 하면 조금 빡셀 듯...