문제: https://www.acmicpc.net/problem/9466

설명

이 문제는 크게 두가지 특징을 만족해야 한다.
1. 혼자 팀을 하고 싶어하는 사람을 선택한 사람은 팀을 이룰 수 없다.
2. 팀을 이루기 위해서는 서로를 선택해야 한다.(서로가 서로를 선택하는 사이클을 갖는다.)

따라서 해당 지점 방문 여부와 팀 완성 여부를 확인한다.
2차원 boolean 배열을 사용하여 구현했다.

1. 입력을 받을 때 인덱스와 가리키는 학생의 인덱스가 같은 경우 -> 팀 완성 배열이 된다.
2. 자신이 가리키는 학생이 이미 방문했지만, 팀을 이룬적이 없는 경우 -> 팀이 완성된다.
   여기서 4, 6, 7의 관계가 그렇다.
   

코드

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

public class P9466 {
	static int N;
    static int[] students;
    static boolean[] visited;
    static boolean[] finished;
    static int count;
    
    public static void main(String[] args) throws IOException {
		System.setIn(new FileInputStream("src/Algorithm/P9466/input.txt"));
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        StringBuilder sb = new StringBuilder();
        
        int T = Integer.parseInt(br.readLine());
        
        for (int i = 0; i < T; i++) {
        	N = Integer.parseInt(br.readLine());
            students = new int[N+1];
            visited = new boolean[N+1];
            finished = new boolean[N+1];
            
            count = 0;
            
			st = new StringTokenizer(br.readLine());
            for (int j = 1; j <= N; j++) {
                students[j] = Integer.parseInt(st.nextToken());
            }
            
            // 모든 숫자 확인
            for (int j = 1; j <= N; j++) {
            	// DFS로 팀이 구성되었다면 확인할 필요 없음
            	if (!finished[j]) {
                	DFS(j);
				}
			}
            sb.append(N - count).append("\n");
		}
        System.out.println(sb);
	}
    
    private static void DFS(int now) {
    	// 이미 방문한 경우 -> 팀 편성 되었다.
        if (visited[now]) {
        	finished[now] = true;
            count++;
		}
        // 방문안한 경우 -> 탐색 시작하는데 또 방문하면 안되니까 방문 표시
        else {
        	visited[now] = true;
		}
        // 다음 학생이 팀 결정을 못했다면 -> 탐색한다.
        if (!finished[students[now]]) {
        	DFS(students[now]);
		}
       	visited[now] = true;
        finished[now] = true;	// 팀 구성 가능 여부 확인
	}
}