[백준] 9466번 텀 프로젝트 (gold 3

import java.util.*;
import java.io.*;

public class Main{
    static int[] num;
    static ArrayList<Integer> arr=new ArrayList<>();
    static int[] go;
    static boolean[] check;
    static Queue<Integer> que=new LinkedList<>();
    public static void main(String[] args) throws IOException{
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw=new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;

        int t=Integer.valueOf(br.readLine());
        for(int cs=0; cs<t; cs++){
            int n=Integer.valueOf(br.readLine());
            num=new int[n+1];
            for(int i=1; i<=n; i++){
                num[i]=i;
            }

            int answer=0;
            st=new StringTokenizer(br.readLine());
            arr.clear();
            go=new int[n+1];
            check=new boolean[n+1];
			
            //유니온 파인드. s1==s1케이스나 
            //신장트리에서 사이클이 생길때 집합의 대표정점을 표시하고 arr에 넣어둠
            for(int i=1; i<=n; i++){
                int temp=Integer.valueOf(st.nextToken());
                go[i]=temp;
                int fa=Find(i);
                int fb=Find(temp);
                if(fa==fb){
                    if(!check[fa]) {
                        check[fa] = true;
                        arr.add(fa);
                    }
                }
                else{
                    Union(i,temp);
                }
            }

			//arr에 들어온 수는 결국 그 수가 사이클에 포함된 것이므로 
            //그 수를 이용해서 사이클을 돌면서 해당되는 수들을 지우면됨.
            //이렇게하는 경우는 4 6 7번방이 각각 7 7 6 일 경우,
            //4,6,7번방은 유니온 파인드로 하나의 대표정점이 저장되지만,
            //실상의 사이클은 6,7번만 해당되므로, 대표정점으로 사이클을 돌리면서 
            //사이클에 포함되는 정점만 지우기
            que.clear();
            for(int i=0; i<arr.size(); i++){
                int aN=arr.get(i);
                if(check[aN]){
                    que.offer(aN);
                    while(!que.isEmpty()){
                        int a=go[que.poll()];
                        if(check[a]){
                            continue;
                        }
                        check[a]=true;
                        que.offer(a);
                    }
                }
            }

            for(int i=1; i<=n; i++){
                if(!check[i]){
                    answer++;
                }
            }

            bw.write(answer+"\n");
        }
        bw.flush();
    }

    public static int Find(int v){
        if(num[v]==v){
            return v;
        }
        else{
            return num[v]=Find(num[v]);
        }
    }

    public static void Union(int a, int b){
        int fa=Find(a);
        int fb=Find(b);
        if(fa!=fb){
            num[fa]=fb;
        }
    }
}