bj2668(숫자 고르기)-dfs **복습**

https://www.acmicpc.net/problem/2668

 

이 문제는 dfs로 풀면 된다.

총 2번의 dfs를 돌리는 것을 생각했다.

첫 번째 dfs는 루프가 있을때까지 돌린다.

두 번째 dfs는 루프가 있을때, 그 루프의 모든 원소를 체크한다.

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashSet;
import java.util.Set;

public class Main {
    /**
     * 순서를 저장해야함
     * 순서에서 자르면 뎀
     */
    static int N;
    static int[] nums;
    static int[] unions;
    static BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
    public static void main(String[] args) throws IOException {
        initialize();
        int[] answers = solve();
        for(int i : answers){
            System.out.println(i);
        }
    }

    private static int[] solve() {
        for(int i = 1; i <= N; i++){
            Set<Integer> union = new HashSet<>();
            if(unions[i] != 0)continue;
            int start = firstDfs(i, union);
            unions[start] = i;
            secondDfs(start, nums[start], i);
        }

        int size = getSize();
        int[] answers = new int[size+1];
        answers[0] = size;
        int j = 1;
        for(int i = 1; i <= N; i++){
            if(unions[i] != 0){
                answers[j++] = i;
            }
        }
        return answers;
    }

    private static int getSize() {
        int size = 0;
        for(int i = 1; i <= N; i++){
            if(unions[i] != 0)size++;
        }
        return size;
    }

    private static void secondDfs(int start, int temp, int i) {
        if(temp == start){
            unions[temp] = i;
            return;
        }
        unions[temp] = i;
        secondDfs(start, nums[temp], i);
    }

    private static int firstDfs(int i, Set<Integer> union) {
        if(union.contains(i))return i;
        union.add(i);
        return firstDfs(nums[i], union);
    }

    private static void initialize() throws IOException {
        N = Integer.parseInt(bufferedReader.readLine());
        nums = new int[N+1];
        unions = new int[N+1];
        for(int i = 1; i <= N; i++){
            nums[i] = Integer.parseInt(bufferedReader.readLine());
        }
    }
}