#백준_2668 숫자고르기 - Java 자바

# 유형 : 그래프탐색, DFS

# 숫자가 부분 수열을 이룬다. 이 문제를 다르게 생각하면 숫자들이 사이클을 이룬다면 부분 수열이 된다. 따라서 DFS로 사이클을 체크해주면 된다.

 

package bj;
 
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
 
public class p2668 {
    static int N;
    static int arr[];
    static int result=0;
    static boolean visit[],cycle[];
    public static void main(String[] args) throws NumberFormatException, IOException {
    
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        
        arr = new int[N+1];
        visit = new boolean[N+1];
        cycle = new boolean[N+1];
        
        for(int i=1; i<=N; i++) {
            arr[i] = Integer.parseInt(br.readLine());
        }
        
        for(int i=1; i<=N; i++) {
            for(int j=1; j<=N; j++)
                visit[j] = cycle[j];
            dfs(i,arr[i]);
        }
        System.out.println(result);
        for(int i=1; i<=N; i++) {
            if(cycle[i])
                System.out.println(i);
        }
    }
    
    public static boolean dfs(int start_val, int arr_val) {
//        System.out.println(start_val + " "+arr_val);
        if(visit[arr_val] == true)
            return false;
        
        visit[arr_val] = true;
        
        if(start_val == arr_val || dfs(start_val, arr[arr_val])) {
            result++;
//            System.out.println(start_val+" "+"cehck"+ arr_val);
            cycle[arr_val] = true;
            return true;
        }
        return false;
    }
}